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

Leave a Reply