Bitmask: come determinare se un solo bit è impostato

Question

Se ho una maschera di bit di base ...

cat = 0x1; 
dog = 0x2; 
chicken = 0x4; 
cow = 0x8; 

// OMD has a chicken and a cow 
onTheFarm = 0x12; 

... come posso controllare se un solo animale (vale a dire un bit) è impostato?

Il valore di onTheFarm deve essere 2 ⁿ, ma come posso verificarlo a livello di codice (preferibilmente in Javascript)?

Answer 1

È possibile contare il numero di bit che sono impostati in un valore intero non negativo con questo codice (adattato a JavaScript da this answer):

function countSetBits(i) 
{ 
    i = i - ((i >> 1) & 0x55555555); 
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333); 
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; 
} 

Dovrebbe essere molto più efficiente dell'esame di ogni singolo bit. Tuttavia, non funziona se il bit di segno è impostato su i.

EDIT (tutto il credito al commento di Pointy):

function isPowerOfTwo(i) { 
    return i > 0 && (i & (i-1)) === 0; 
} 

Answer 2

Devi controllare pezzo per pezzo, con una funzione più o meno così:

function p2(n) { 
    if (n === 0) return false; 
    while (n) { 
    if (n & 1 && n !== 1) return false; 
    n >>= 1; 
    } 

    return true; 
} 

Alcune CPU set di istruzioni hanno incluso un'operazione di "contare impostare i bit" (l'antica serie CDC Cyber ​​è stato uno) . È utile per alcune strutture dati implementate come raccolte di bit. Se hai un set implementato come una stringa di numeri interi, con posizioni di bit corrispondenti a elementi del tipo di dati impostato, ottenere la cardinalità implica contare i bit.

modificare wow esaminando la risposta di Ted Hopp mi sono imbattuto in questo:

function p2(n) { 
    return n !== 0 && (n & (n - 1)) === 0; 
} 

Questo è da this awesome collection of "tricks". Cose come questo problema sono buone ragioni per studiare la teoria dei numeri :-)

Answer 3

Se stai cercando di vedere se solo si trova un singolo bit, è possibile usufruire di logarithms, come segue:

var singleAnimal = (Math.log(onTheFarm)/Math.log(2)) % 1 == 0; 

Math.log(y)/Math.log(2) trova x in 2^x = y e x % 1 ci dice se x è un numero intero. x sarà un numero intero solo se è impostato un singolo bit e, quindi, viene selezionato un solo animale.