Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

Solution1:

Run time complexity is O(n), constant space.

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        if(n == 0) {
            return 0;
        }
        
        int count = 0;
        while(n != 0) {
            if((n & 1) == 1) {
                count++;
            }
            n = n >>> 1;  //unsigned right shift(强制补0)
        }
        
        return count;
    }
}

Solution2: 

The bitwise and of x with x − 1 differs from x only in zeroing out the least significant nonzero bit: subtracting 1 changes the rightmost string of 0s to 1s, and changes the rightmost 1 to a 0. If x originally had n bits that were 1, then after only n iterations of this operation, x will be reduced to zero. 

Run time complexity is O(n), n is number of 1s, constant space.

Check Hamming Weight on Wiki: http://en.wikipedia.org/wiki/Hamming_weight

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        if(n == 0) {
            return 0;
        }
        
        int count = 0;
        while(n != 0) {
            n = (n & (n - 1));
            count++;
        }
        
        return count;
    }
}