Count set bits in an integer

The problem, simply

Every number is stored as a row of bits, 0s and 1s. A bit that is 1 is called a set bit.

You get a number n. Give back how many of its bits are 1. For example 13 is 1101, which has three 1s.

A story to remember it

Picture it

Examples

Way 1: the simple way

Check the last bit, then slide the number right, and repeat.

1. n & 1 is 1 when the last bit is on. If so, add 1 to the count.
2. Slide everything one place right with n >>>= 1. The old last bit falls off.
3. Stop when n is 0.

class Solution {
    public static int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;   // add 1 if the last bit is on
            n >>>= 1;         // slide right, pulling in a 0 on the left
        }
        return count;
    }
}

How long it takes: one round for every bit up to the highest 1, O(log n), at most 32 rounds. Extra room: O(1).

Way 2: the clever way

The trick is n & (n - 1). It wipes out the lowest 1 of n and leaves every other bit alone.

Why? Taking 1 away from n finds the lowest 1, turns it into 0, and turns all the 0s under it into 1s. Everything above stays the same. So n and n - 1 agree above that spot and are opposite from that spot down. AND keeps only bits that are 1 in both, so the bottom part becomes all 0s.

1. While n is not 0, do n = n & (n - 1) and add 1 to the count.
2. The count is the number of 1s, because each round removed exactly one.

class Solution {
    public static int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            n &= n - 1;       // wipe out the lowest 1
            count++;
        }
        return count;
    }
}

How long it takes: one round per set bit. If n has k ones, that is O(k), which is never worse than Way 1 and much better for numbers with few ones. Extra room: O(1).

Watch out for

• Writing n & n - 1 without thinking about order. In Java - happens before &, so it works, but n & (n - 1) is clearer.
• Java has Integer.bitCount(n) and Long.bitCount(n). Fine in real code, but interviewers want the loop.
• For a long, use long everywhere, and 1L if you build masks.

What interviewers ask next

• Count bits for every number from 0 to n? Use a table: bits[i] = bits[i >> 1] + (i & 1). Each number is its half plus its last bit, so the whole table is O(n).
• Can it be faster for many queries? Precompute the count for all 256 byte values, then answer any int with four lookups, one per byte.
• How does Integer.bitCount work? It adds bits in pairs, then pairs of pairs, and so on, with masks like 0x55555555 and 0x33333333. That is 5 steps for 32 bits, no loop.
• Is a number a power of two? It is when it is above 0 and has exactly one set bit, which means n & (n - 1) == 0.

Remember this

Grown-up words: lit candles are set bits, the count is the population count or Hamming weight, the plain way is a shift loop, and the candle trick is Brian Kernighan's algorithm.