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.
Tuesday, July 06, 2010
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment