bitmask: làm thế nào để xác định nếu chỉ có một bit được thiết lập

Question

Nếu tôi có một bitmask cơ bản ...

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

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

... làm thế nào tôi có thể kiểm tra nếu chỉ có một động vật (ví dụ: một bit) được thiết lập?

Giá trị của onTheFarm phải là 2 ⁿ, nhưng làm cách nào tôi có thể kiểm tra xem chương trình đó (tốt nhất là trong Javascript)?

Answer 1

Bạn có thể đếm số lượng các bit được đặt trong một giá trị số nguyên không âm với mã này (thích nghi với JavaScript từ this answer):

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

Nó sẽ hiệu quả hơn nhiều so với việc kiểm tra từng bit riêng lẻ. Tuy nhiên, nó không hoạt động nếu bit dấu được đặt trong i.

EDIT (tất cả tín dụng để bình luận chóp của):

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

Answer 2

Bạn phải kiểm tra từng chút một, với một hàm nhiều hay ít như thế này:

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

    return true; 
} 

Một số CPU bộ giảng dạy đã bao gồm một "đếm thiết lập bit" hoạt động (CDC Cyber ​​phim cổ trang là một) . Nó rất hữu ích cho một số cấu trúc dữ liệu được thực hiện như các bộ sưu tập bit. Nếu bạn đã có một tập hợp được thực hiện như một chuỗi các số nguyên, với các vị trí bit tương ứng với các phần tử của kiểu dữ liệu được thiết lập, thì việc nhận được số lượng thẻ bao gồm đếm bit.

chỉnh sửa wow nhìn vào câu trả lời Ted Hopp của tôi stumbled trên này:

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

Đó là từ this awesome collection of "tricks". Những điều như vấn đề này là lý do chính đáng để nghiên cứu lý thuyết số :-)

Answer 3

Nếu bạn đang tìm kiếm để xem nếu chỉ một chút đơn được thiết lập, bạn có thể tận dụng lợi thế của logarithms, như sau:

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

Math.log(y)/Math.log(2) tìm số x trong 2^x = y và x % 1 cho chúng tôi biết nếu x là một số nguyên. x sẽ chỉ là một số nguyên nếu một bit được đặt và do đó, chỉ có một động vật được chọn.