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.

Navie method:

do a BIT AND with 1, this will get the rightmost bit, if the result is one, increase the count, then shift the rightmost bit until the number reaches 0;

public int hammingWeightNaive(int n) {
        if (n==0) {
            return 0;
        }

        int count = 0;
        while(n!=0) {
            if ((n&1)==1) {
                count = count + 1;
            }
            n = n>>1;
        }
        return count;
    }

Brian Kernighan’s Algorithm:

Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the righmost set bit). So if we subtract a number by 1 and do bitwise & with itself (n & (n-1)), we unset the righmost set bit. If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit count.

1001: (2 set bits)

1001 & 1000 = 1000 1000 & 0111 = 0000

111: (3 set bits)

111 & 110 = 110 110 & 101 = 100 100 & 011 = 000

public int hammingWeight(int n) {
        if (n==0) {
            return 0;
        }

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