This is No.191 in LeetCode.
This is the best solution I think, easy to understand and has a straight logic:
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int num_one = 0;
//001000000010001
while( n > 0 ){
// 00010011 & 00000001
num_one += n & 1;
n = n >> 1;
}
return num_one;
}
}
To compare the original number with 1, for example 00001010 & 00000001, if the right-most bit is 1 then the result would be 1, otherwise 0.
And when it complete comparison each time, shift rightward one bit to get new number waiting for comparison.
But here is a problem that Java doesn’t have unsigned integer type, so when n is a signed integer, then the program would skip the while loop and return 0. To solve this problem, here is another way to solve the question:
public int hammingWeight(int n) {
int bits = 0;
int mask = 1;
for (int i = 0; i < 32; i++) {
if ((n & mask) != 0) {
bits++;
}
mask <<= 1;
}
return bits;
}
In this case we don’t care if it is greater than 0, we compare each bit in n.
Or we can do a small changes on the first version:
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int num_one = 0;
//001000000010001
while( n != 0 ){
// 00010011 & 00000001
num_one += n & 1;
n = n >>> 1;
//System.out.println("num_one:" + num_one);
}
return num_one;
}
}
The difference between >>> and >>
-
Signed Right shift operator (>>) –
Shifts the bits of the number to the right and fills 0 on voids left as a result. The leftmost bit depends on the sign of initial number. Similar effect as of dividing the number with some power of two.For example, Example 1: a = 10 a>>1 = 5 Example 2: a = -10 a>>1 = -5 We preserve the sign bit.
-
Unsigned Right shift operator (>>>) –
Shifts the bits of the number to the right and fills 0 on voids left as a result. The leftmost bit is set to 0. (>>>) is unsigned-shift; it’ll insert 0. (>>) is signed, and will extend the sign bit.For example, Example 1: a = 10 a>>>1 = 5 Example 2: a = -10 a>>>1 = 2147483643 DOES NOT preserve the sign bit.