15

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)?

Tim
  • 6,281
  • 3
  • 39
  • 49
  • Check out [this question](http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer). Not javascript-specific, but interesting. – Rob I Apr 11 '13 at 14:46
  • Thanks Rob, just found this (it looks a bit more straight forward) http://stackoverflow.com/questions/1053582/how-does-this-bitwise-operation-check-for-a-power-of-2 – Tim Apr 11 '13 at 14:53
  • 3
    Just FYI, `OMD` = [`Old MacDonald`](https://en.wikipedia.org/wiki/Old_MacDonald_Had_a_Farm). – rvighne May 18 '14 at 23:14
  • 3
    @rvighne: I/O, I/O, null... – Juha Untinen Apr 19 '16 at 05:49

3 Answers3

11

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;
}
Community
  • 1
  • 1
Ted Hopp
  • 232,168
  • 48
  • 399
  • 521
  • 2
    Wow that's pretty good. Looking into that, I found [this reference](http://aggregate.org/MAGIC/#Is%20Power%20of%202) for this particular question, and it looks even better! – Pointy Apr 11 '13 at 15:05
3

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 :-)

Pointy
  • 405,095
  • 59
  • 585
  • 614
0

If you're looking to see if only a single bit is set, you could take advantage of logarithms, as follows:

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

Math.log(y) / Math.log(2) finds the x in 2^x = y and the x % 1 tells us if x is a whole number. x will only be a whole number if a single bit is set, and thus, only one animal is selected.

cmptrgeekken
  • 8,052
  • 3
  • 29
  • 35
  • 1
    Merrily ignoring floating point roundoff, you would conclude that (1<<29) would have more than one bit set: `console.log((Math.log(1<<29) / Math.log(2)) % 1)` prints 3.552713678800501e-15 on my machine. – Ted Hopp Apr 11 '13 at 15:05
  • Interesting. I suppose using `log` in general would be far less efficient than the other techniques outlined as answers anyways. Know of any way to handle the floating point roundoff error? – cmptrgeekken Apr 11 '13 at 18:52
  • Not for this problem. You can read a good overview of the issues in [this article](http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html). It's pretty heavy technically, but worth struggling through if you want a firm understanding of what's going on under the hood with floating point. The TL;DR version is: every floating point operation (even simply representing a number) has an error; design your code accordingly. – Ted Hopp Apr 11 '13 at 21:25