Count total set bits in all numbers from 1 to n

The problem, simply

You get a number n. Write every number from 1 to n in binary. Count all the 1s you wrote, across all those numbers, and give back the total.

For n = 5: 1 is 1, 2 is 10, 3 is 11, 4 is 100, 5 is 101. That is 1 + 1 + 2 + 1 + 2 = 7 ones.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do exactly what the problem says. For each number from 1 to n, count its 1s, and add them up.

1. Loop i from 1 to n.
2. Count the 1s in i by checking the last bit and sliding right.
3. Add to the total.

class Solution {
    public static long countTotalSetBits(int n) {
        long total = 0;
        for (int i = 1; i <= n; i++) {
            int x = i;
            while (x != 0) {
                total += x & 1;   // add 1 if the last bit is on
                x >>>= 1;
            }
        }
        return total;
    }
}

How long it takes: n numbers, each with up to log n bits, O(n log n). For n near a billion that is about 30 billion steps. Extra room: O(1).

Way 2: the clever way

Count down each column instead of across each row. Include 0 at the top, which adds no 1s but makes the patterns start cleanly. So there are n + 1 rows.

Column i repeats a block of 2^(i+1) rows: first 2^i zeros, then 2^i ones.

1. Full blocks: there are (n + 1) / 2^(i+1) of them, and each holds 2^i ones.
2. Left over rows: there are (n + 1) % 2^(i+1) of them. The first 2^i of those are zeros, so they add max(0, leftover - 2^i) ones.
3. Add both parts for every column whose 2^i is at most n.

class Solution {
    public static long countTotalSetBits(long n) {
        long total = 0;
        for (long half = 1; half <= n; half <<= 1) {   // half = 2^i for column i
            long block = half << 1;                     // zeros then ones, 2^(i+1) rows
            long rows = n + 1;                          // the numbers 0 to n
            total += (rows / block) * half;             // full blocks
            total += Math.max(0, rows % block - half);  // the part that is left over
        }
        return total;
    }
}

How long it takes: one round per column, and n has about log n columns, O(log n). For a billion that is 30 rounds instead of 30 billion steps. Extra room: O(1).

Another way: split at the biggest power of two

Let 2^a be the biggest power of two that is at most n.

• The numbers from 0 to 2^a - 1 fill a columns completely, and each column is half ones, so they hold a * 2^(a-1) ones.
• Every number from 2^a to n has the top bit on. That is n - 2^a + 1 more ones.
• Under that top bit, those numbers count again from 0 to n - 2^a. Solve that smaller problem the same way.

class Solution {
    public static long countTotalSetBits(long n) {
        if (n <= 0) return 0;
        int a = 63 - Long.numberOfLeadingZeros(n);    // 2^a is the biggest power of two <= n
        long top = 1L << a;
        long below = a == 0 ? 0 : (long) a << (a - 1); // a * 2^(a-1), all ones below 2^a
        return below + (n - top + 1) + countTotalSetBits(n - top);
    }
}

Each call removes the top bit of n, so there are at most log n calls: O(log n) time and O(log n) room on the call stack.

Watch out for

• The left over part can be smaller than 2^i. Then it holds only zeros, so take max(0, ...) instead of adding a negative number.
• Totals grow fast, about n log n / 2. Use long for the total.
• In the split way, a * 2^(a-1) must be 0 when a = 0. Guard it on its own: in Java a shift by -1 on a long means a shift by 63, which is never what you want.

What interviewers ask next

• Count 1s for every i from 0 to n separately? Build a table: bits[i] = bits[i >> 1] + (i & 1). That is O(n), and it is a classic.
• Count only the 1s in column k from 1 to n? That is one round of the loop above.
• Count total 1s in a range from L to R? Answer total(R) - total(L - 1).
• Count numbers from 1 to n with exactly k set bits? Walk the bits of n from the top and use combinations, a digit counting idea.

Remember this

Grown-up words: the bulbs are bit positions, the rhythm is a period of 2^(i+1), counting down columns is counting per bit position, and the split method is a divide and conquer on the most significant bit.