int hammingWeight(uint32_t n) {
int count = n ? 1 : 0;
while(n &= (n-1)) count++;
return count;
}
Edit: Updated code to make it more readable. Still 0 ms.
This is a reply to gvikram:
Todd was going for minimal line usage which creates some confusion.
the exact same implementation in a little more human readable format is:
int hammingWeight(uint32_t n) {
int count = 0;
while(n != 0) {
count++;
n=n&(n-1);
}
return count;
}
when n=0 the while loop exits.
much like how n++ = n+1
n&=1 is the same as n=n&(n-1)
n&=(n-1)
As to how it works:
say n is 5
count = 0
5 = 101
n-1 is 4
4 = 100
101 & 100 = 100
count = 1;
n=100
3= 11
100 & 11 = 0
count = 2
exit loop. Success! Every iteration of this loop removes a 1 from the binary value of your number. It;'s very clever
Another example:
n=7
count = 0;
7=111
6=110
111&110=110
count = 1;
n =110
n-1=101
110&101 = 100
count =2
n =100
n-1=11
100&11=0
count =3
Success!
Very clever :)