Maska bitowa: jak określić, czy tylko jeden bit jest ustawiony

Question

Jeśli mam podstawową maskę bitową ...

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

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

... Jak mogę sprawdzić, czy tylko jedno zwierzę (to znaczy jeden bit) jest ustawiony?

Wartość onTheFarm musi wynosić 2 ⁿ, ale jak mogę to sprawdzić programowo (najlepiej w JavaScript)?

Answer 1

można policzyć liczbę bitów, które są ustawione w nieujemnej liczby całkowitej z tym kodem (dostosowany do JavaScript z this answer):

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

Powinno to być znacznie bardziej wydajne niż zbadanie każdego pojedynczo. Jednak nie działa, jeśli bit znaku jest ustawiony w i.

EDIT (wszystkie karty do komentarza pointy za):

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

Answer 2

Trzeba sprawdzić, kawałek po kawałku, z funkcją mniej więcej tak:

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

    return true; 
} 

Niektóre CPU zestawy instrukcji włączyły „liczyć zestaw bitów” operacja (starożytny seria CDC Cyber ​​był jednym) . Jest to przydatne w przypadku niektórych struktur danych zaimplementowanych jako kolekcje bitów. Jeśli masz zestaw zaimplementowany jako ciąg liczb całkowitych, z pozycjami bitowymi odpowiadającymi elementom ustawionego typu danych, to liczenie bitów obejmuje liczenie bitów.

edit wow patrząc na odpowiedzi Teda HOPP za natknąłem to:

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

To od this awesome collection of "tricks". Rzeczy takie jak ten problem są powody do studiowania teorii liczb :-)

Answer 3

Jeśli szukasz, aby zobaczyć czy jeden bit jest ustawiony tylko, można skorzystać z logarithms, co następuje:

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

Math.log(y)/Math.log(2) znajduje x w 2^x = y, a x % 1 mówi nam, czy x jest liczbą całkowitą. x będzie liczbą całkowitą tylko wtedy, gdy zostanie ustawiony pojedynczy bit, a zatem wybrane zostanie tylko jedno zwierzę.