Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Bitmask: how to determine if only one bit is set

If I have a basic bitmask...

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

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

...how can I check if only one animal (i.e. one bit) is set?

The value of onTheFarm must be 2n, but how can I check that programmatically (preferably in Javascript)?

like image 546
Tim Avatar asked Apr 11 '13 14:04

Tim


People also ask

How do you know if a single bit is set?

Check whether the K-th bit is set or not Using Left Shift Operator: To solve the problem follow the below idea: Left shift given number 1 by k-1 to create a number that has only set bit as k-th bit. If bitwise AND of n and temp is non-zero, then result is SET else result is NOT SET.

How do I unset a particular bit?

Use the bitwise AND operator (&) to clear a bit. number &= ~(1 << x); That will clear bit x. You must invert the bit string with the bitwise NOT operator (~), then AND it.

Is Bitmask and bit manipulation same?

Bitmasks are a type of bit manipulation, usually performed using the bitwise AND operator to read or clear a specific number of bits. It can also refer to setting, clearing, and toggling individual bits in a bit field.


2 Answers

You can count the number of bits that are set in a non-negative integer value with this code (adapted to JavaScript from this answer):

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

It should be much more efficient than examining each bit individually. However, it doesn't work if the sign bit is set in i.

EDIT (all credit to Pointy's comment):

function isPowerOfTwo(i) {
    return i > 0 && (i & (i-1)) === 0;
}
like image 54
Ted Hopp Avatar answered Sep 18 '22 17:09

Ted Hopp


You have to check bit by bit, with a function more or less like this:

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

  return true;
}

Some CPU instruction sets have included a "count set bits" operation (the ancient CDC Cyber series was one). It's useful for some data structures implemented as bit collections. If you've got a set implemented as a string of integers, with bit positions corresponding to elements of the set data type, then getting the cardinality involves counting bits.

edit wow looking into Ted Hopp's answer I stumbled across this:

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

That's from this awesome collection of "tricks". Things like this problem are good reasons to study number theory :-)

like image 25
Pointy Avatar answered Sep 18 '22 17:09

Pointy