Topics › Bit Manipulation › Learn Bit Manipulation

Count the Number of Set Bits

Easy TUF ID 243 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

The number of set bits of an integer is how many 1s appear in its binary representation; it is also called the popcount or Hamming weight. This article answers two closely related questions that both go by this title on the sheets:

• Part A. Given an integer n, return the number of set bits in n. A negative n is counted as its 32-bit two’s-complement pattern, so -1 has 32 set bits.
• Part B. Given n ≥ 0, return the total number of set bits across all the numbers 1, 2, ..., n. This is the version behind the sheet’s practice link, and its answer needs a long for large n.

Constraints: n fits in a 32-bit signed integer; for Part B, 0 ≤ n ≤ 10^9.

Example 1 (Part A)

n = 13
answer = 3           // 13 = 1101

Example 2 (Part A)

n = 8
answer = 1           // 8 = 1000

Example 3 (Part B)

n = 6
answer = 9           // 1=1, 10=1, 11=2, 100=1, 101=2, 110=2, total 1+1+2+1+2+2

Approach 1: Brute force, read the lowest bit and shift it out

Intuition. Look at bit 0, add it to a counter, then shift the number right so bit 1 becomes bit 0, and repeat until the number is zero. The unsigned shift >>> fills with zeros, so even a negative number reaches zero after at most 32 rounds. With the signed >> a negative number would keep its sign bit forever and the loop would never end.

Algorithm.

1. Set count = 0.
2. While n != 0: add n & 1 to count, then n >>>= 1.
3. Return count.

static int bruteForce(int n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>>= 1;                       // unsigned shift so a negative n terminates after 32 rounds
    }
    return count;
}

Complexity. Time O(number of bits), up to 32 iterations regardless of how many are set. Space O(1).

Approach 2: Optimal, Brian Kernighan’s loop

Intuition. n - 1 flips the lowest set bit of n to 0 and all the zeros below it to 1; everything above is unchanged. So n & (n - 1) is n with its lowest set bit removed and nothing else touched. Repeat until n is zero and count the rounds: each round removes exactly one 1, so the number of rounds is the popcount. The loop runs once per set bit, not once per bit, which is a real win for sparse numbers like 8 = 1000.

Algorithm.

1. Set count = 0.
2. While n != 0: n &= n - 1, count++.
3. Return count.

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

Dry run on n = 13 = 1101:

Three rounds, three set bits.

Complexity. Time O(k) where k is the number of set bits, at most 32. Space O(1).

Approach 3: Constant time with a lookup table

Intuition. An int is four bytes, and there are only 256 possible bytes. Precompute the popcount of every byte once, then answer any query with four table lookups and three additions. The table itself is built with a one-line recurrence: the popcount of b is the popcount of b >> 1 plus the lowest bit of b.

Algorithm.

1. Build TABLE[0..255] with TABLE[b] = TABLE[b >> 1] + (b & 1).
2. Return TABLE[n & 0xFF] + TABLE[(n >>> 8) & 0xFF] + TABLE[(n >>> 16) & 0xFF] + TABLE[n >>> 24].

static int[] buildTable() {
    int[] t = new int[256];
    for (int b = 1; b < 256; b++) t[b] = t[b >> 1] + (b & 1);
    return t;
}

static int lookupTable(int n) {
    return TABLE[n & 0xFF] + TABLE[(n >>> 8) & 0xFF] + TABLE[(n >>> 16) & 0xFF] + TABLE[n >>> 24];
}

Complexity. Time O(1) per query after an O(256) one-time setup. Space O(256).

The last lookup uses n >>> 24 without a mask because the unsigned shift already leaves only the top byte. In production code, Integer.bitCount(n) is the right call: the JVM compiles it to a single POPCNT instruction. Knowing the loop versions matters because interviewers ask for them and because the n & (n - 1) idea shows up everywhere.

Counting over a range: total set bits in 1..n

Adding up optimal(i) for every i from 1 to n works and is the natural brute force:

static long totalBruteForce(int n) {
    long total = 0;
    for (int i = 1; i <= n; i++) total += optimal(i);
    return total;
}

That is O(n log n) and far too slow for n = 10^9. The way out is to stop thinking about numbers and think about bit positions.

Intuition. Write the numbers 0, 1, 2, ... in a column. Bit 0 goes 0, 1, 0, 1, ...: a period of 2, half zeros then half ones. Bit 1 goes 0, 0, 1, 1, 0, 0, 1, 1, ...: period 4. In general bit i is 0 for 2^i consecutive numbers and then 1 for 2^i numbers, with period 2^(i+1). Over the n + 1 numbers 0..n (zero contributes nothing, so this equals the count over 1..n) there are (n + 1) / 2^(i+1) complete periods, each contributing 2^i ones, plus one unfinished period of (n + 1) mod 2^(i+1) numbers whose first 2^i are zeros and the rest ones.

Algorithm.

1. For each bit position i from 0 to 30:
   • half = 2^i, period = 2^(i+1).
   • full = (n + 1) / period * half.
   • partial = (n + 1) mod period - half, clipped at 0.
   • Add full + partial to the total.
2. Return the total.

static long totalOptimal(int n) {
    long total = 0;
    for (int i = 0; i < 31; i++) {
        long half = 1L << i, period = half << 1;
        long full = (n + 1L) / period * half;          // complete periods, each contributes 2^i ones
        long partial = (n + 1L) % period - half;        // the unfinished period: ones only after its zero-run
        total += full + Math.max(0L, partial);
    }
    return total;
}

Dry run on n = 6 (so n + 1 = 7 numbers, 0..6):

Total 9, matching the example (1, 3, 5 have bit 0; 2, 3, 6 have bit 1; 4, 5, 6 have bit 2).

Complexity. Time O(log n), 31 iterations of constant work. Space O(1).

A second linear-in-bits method is the classic recursion. Let 2^x be the largest power of two with 2^x ≤ n. Among 0 .. 2^x - 1 every one of the x low positions is set in exactly half the numbers, giving x · 2^(x-1) ones. Every number from 2^x to n has bit x set, giving n - 2^x + 1 more. Strip that top bit from those numbers and they become 0 .. n - 2^x, which is the same problem on a smaller input.

static long totalRecursive(int n) {
    if (n <= 0) return 0;
    int x = 0;
    while ((1L << (x + 1)) <= n) x++;                   // 2^x <= n < 2^(x+1)
    long belowTop = x == 0 ? 0 : (long) x * (1L << (x - 1)); // set bits among 0 .. 2^x - 1
    long topBits = n - (1L << x) + 1;                   // bit x is set in every number 2^x .. n
    return belowTop + topBits + totalRecursive(n - (1 << x));
}

For n = 6: x = 2, belowTop = 2 · 2 = 4 (numbers 0..3), topBits = 3 (numbers 4, 5, 6), then recurse on 2: x = 1, belowTop = 1, topBits = 1, recurse on 0. Total 4 + 3 + 1 + 1 = 9. Each call removes the highest bit of n, so the depth is at most 31.

Edge cases and pitfalls

• n = 0. Zero set bits, and an empty range in Part B; all methods return 0.
• Negative numbers in Part A. Use >>> in the shifting loop; with >> the loop on -1 never terminates. Kernighan’s loop is fine because n & (n - 1) on a negative still removes a bit each round and reaches 0 after at most 32 rounds. Integer.MIN_VALUE has exactly one set bit.
• Overflow in Part B. The total for n = 10^9 is 14,846,928,141, well beyond int. Accumulate in long, and compute n + 1 as a long so that n = Integer.MAX_VALUE does not wrap to a negative.
• Off-by-one in the period formula. Counting over 0..n means n + 1 numbers; using n instead undercounts whenever n itself is odd or has the bit in question set.
• x = 0 in the recursion. 2^(x-1) would be 2^-1; the explicit x == 0 ? 0 branch avoids shifting by a negative amount.
• Shift by 32. 1 << 32 is 1 in Java. The loops here stop at 31, and the long constants 1L << i are used wherever i can reach 31.

Related problems

• Introduction to Bits and Tricks introduces the n & (n - 1) identity.
• Check if a Number is Power of 2 or Not is “is the popcount exactly one”.
• Minimum Bit Flips to Convert Number is the popcount of an XOR.
• Number of 1 Bits and Counting Bits are the LeetCode forms of Part A and of the per-number table for 0..n.