Bitmask: Wie bestimmen, ob nur ein Bit

Question

gesetzt Wenn ich eine grundlegende bitmask haben ...

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

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

... wie kann ich überprüfen, ob nur ein Tier (das heißt ein Bit) gesetzt?

Der Wert von onTheFarm muss 2 ⁿ sein, aber wie kann ich das programmgesteuert (vorzugsweise in Javascript) überprüfen?

Answer 1

studieren Sie die Anzahl der Bits zählen kann, die in einer nicht-negativen Integer-Wert mit diesem Code (angepasst an JavaScript von this answer) festgelegt sind:

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

Es sollte viel effizienter sein, als jedes Bit einzeln zu untersuchen. Es funktioniert jedoch nicht, wenn das Vorzeichenbit in i festgelegt ist.

EDIT (alle Zipfel Kommentar Kredit):

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

Answer 2

Sie haben etwas zu überprüfen, indem Sie Bit, mit einer Funktion mehr oder weniger wie folgt aus:

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

    return true; 
} 

Einige CPU-Befehlssätze enthalten sind, einen „gesetzten Bits zählen“ Betrieb (die alte CDC Cyber-Serie war ein) . Es ist nützlich für einige Datenstrukturen, die als Bit-Sammlungen implementiert sind. Wenn Sie einen Satz als eine Folge von ganzen Zahlen implementiert haben, wobei die Bitpositionen Elementen des eingestellten Datentyps entsprechen, dann beinhaltet das Erhalten der Kardinalität das Zählen von Bits.

bearbeiten wow Blick in Ted Hopps Antwort, die ich über diese gestolpert:

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

Das von this awesome collection of "tricks" ist. Dinge wie dieses Problem gibt gute Gründe, Zahlentheorie :-)

Answer 3

Wenn Sie schauen, zu sehen, ob nur ein einziges Bit gesetzt ist, können Sie die Vorteile von logarithms nehmen könnte, wie folgt:

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

Math.log(y)/Math.log(2) findet die x in 2^x = y und die x % 1 sagt uns, wenn x eine ganze Zahl ist. x ist nur eine ganze Zahl, wenn ein einzelnes Bit gesetzt ist und somit nur ein Tier ausgewählt ist.