Tuesday, July 06, 2010

badassery with bits: counting 1 bits

I was recently looking at some code to count the number of bits in an integer that are set to 1. Here is the method:

int = getARandomInt();
while(n!=0){
   n &= n-1;
   count++;
}
print("There are "+count+" bits turned on.");

Can you figure out why it works?

hint: negative one has every bit turned on because negating a number is to take it's two's complement (which flips every bit), and add 1. Watch what happens with the carry bit when you add n to -1.

No comments:

Post a Comment