Solution


Approach #1 (Loop and Flip) [Accepted]

Algorithm

The solution is straight-forward. We check each of the bits of the number. If the bit is , we add one to the number of -bits.

We can check the bit of a number using a bit mask. We start with a mask , because the binary representation of is,

Clearly, a logical AND between any number and the mask gives us the least significant bit of this number. To check the next bit, we shift the mask to the left by one.

And so on.

Java

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

Complexity Analysis

The run time depends on the number of bits in . Because in this piece of code is a 32-bit integer, the time complexity is .

The space complexity is , since no additional space is allocated.


Approach #2 (Bit Manipulation Trick) [Accepted]

Algorithm

We can make the previous algorithm simpler and a little faster. Instead of checking every bit of the number, we repeatedly flip the least-significant -bit of the number to , and add to the sum. As soon as the number becomes , we know that it does not have any more -bits, and we return the sum.

The key idea here is to realize that for any number , doing a bit-wise AND of and flips the least-significant -bit in to . Why? Consider the binary representations of and .

Number of 1 Bits

Figure 1. AND-ing and flips the least-significant -bit to 0.

In the binary representation, the least significant -bit in always corresponds to a -bit in . Therefore, anding the two numbers and always flips the least significant -bit in to , and keeps all other bits the same.

Using this trick, the code becomes very simple.

Java

public int hammingWeight(int n) {
    int sum = 0;
    while (n != 0) {
        sum++;
        n &= (n - 1);
    }
    return sum;
}

Complexity Analysis

The run time depends on the number of -bits in . In the worst case, all bits in are -bits. In case of a 32-bit integer, the run time is .

The space complexity is , since no additional space is allocated.

Analysis written by: @noran.