Number of 1 Bits

Simple problem but has multiple solutions.

The first is that we just iterate over all bits and count the ones:

public class NumberOfOneBits {
    public int hammingWeight(int n) {
        int count = 0;
        for(int i = 0; i < 32; i++) {
            if (n & 1 == 1) count++;
            n >>= 1;
        }
        return count;
    }
}

This solution is simple but it depends on the integer's type. It demands that the integer is 32 bits so it need to be modified in different language and machine architecture. The loop executes the fixed amount of times no matter which integer the number is and is thought not time efficient enough.

One alternative solution might be make use of an knowledge that n & (n - 1) returns an integer that all bits is the same as n except the first 1 at the lowest bit position turned into 0. So everytime we perform a n = n & (n - 1), there will be one less 1 in the binary representation of n.

public class NumberOfOneBits {
    // 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;
    }
}

In the code above, n & (n - 1) is in fact equivalent to n & ~(n & -n) as n & -n will generate the integer with only the lowest 1 bit in n to left 1 and all other bits become 0.