For example, the 32-bit integer ’11' has binary representation
00000000000000000000000000001011
, so the function should return 3.Naive Way: To go through each bit using a mask will take 32 unit time. However, there is a way that runs faster, x & (x-1), which removes the right most 1 from x. For reference, see low-level-bit-hacks
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while(n != 0){
n = n & (n-1);
count++;
}
return count;
}
}
No comments:
Post a Comment