# Number of 1 Bits

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++;
}
}
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. ``````