cf.completefrontend
BIT MANIPULATION · CORE

Counting set bits

Count how many bits are 1 in a number by clearing the lowest set bit until nothing is left, or build counts for every number from smaller ones.

Time O(k) for one number, O(n) for the tableSpace O(1) and O(n)4 practice problemsStep-through picture

The idea

The number of 1 bits in a number is called its population count, or popcount. 13 is 1101, so its popcount is 3. If a number is a mask of flags, its popcount is how many flags are on.

The slow way checks all 32 bits one by one. A faster way uses x & (x - 1), which clears the lowest 1 bit. Repeat it until x is 0, and count the steps: the loop runs once per 1 bit, not 32 times.

To get popcounts for every number from 0 to n, reuse earlier answers. i >> 1 is i with its last bit removed, and that smaller number's count is already known. So bits[i] = bits[i >> 1] + (i & 1).

An everyday example

Blowing out candles from the right

A row of candles stands on a cake, some lit and some not. You count the lit ones by always blowing out the lit candle furthest to the right and adding one to your count. When no candle is lit, your count is the answer. You never waste a breath on a candle that was already out.

How the example maps to the code
In the exampleIn the code
The row of candlesthe bits of x
Blowing out the rightmost lit candlex &= x - 1
Adding one to your countcount++
No candle is litx === 0

From the slow way to counting set bits

  1. Start with the obvious way: look at all 32 positions. For k from 0 to 31, add (x >>> k) & 1. That's always 32 steps, even for x = 1, which has a single 1 bit.
  2. A little better: look at the last bit with x & 1, then shift it away with x >>>= 1, until x is 0. The loop now stops after the highest set bit: 8 steps for 180 (10110100). But it still visits every 0 bit below the top one.
  3. Now notice what x - 1 does: it turns the lowest 1 bit into 0 and every 0 below it into 1, leaving higher bits alone. So x & (x - 1) is x with its lowest 1 bit removed. Repeating it jumps from one 1 bit straight to the next, so the loop runs once per 1 bit: 4 steps for 180.
  4. For every number from 0 to n, reuse earlier answers. i >> 1 is i with its last bit removed, a smaller number whose count is already known, and i & 1 is that last bit. So bits[i] = bits[i >> 1] + (i & 1), one step per number. Those two loops are bit counting.

How it works

  1. Turn the input into an unsigned 32-bit value with x = n >>> 0, so negative numbers count their two's complement bits.
  2. While x is not 0, clear its lowest set bit with x &= x - 1.
  3. Add 1 to count each time.
  4. Return count when x is 0.
  5. For every number up to n: make bits with n + 1 zeros and fill bits[i] = bits[i >> 1] + (i & 1) for i from 1 up.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function countBits(n) {
  2. let x = n >>> 0;
  3. let count = 0;
  4. while (x !== 0) {
  5. x &= x - 1;
  6. count++;
  7. }
  8. return count;
  9. }
  11. function countBitsUpTo(n) {
  12. const bits = new Array(n + 1).fill(0);
  13. for (let i = 1; i <= n; i++) {
  14. bits[i] = bits[i >> 1] + (i & 1);
  15. }
  16. return bits;
  17. }

How fast it is

TimeO(k) for one number, O(n) for the table
Extra memoryO(1) and O(n)

The loop runs once per set bit, k of them, at most 32. The table fills each entry with one addition from an earlier entry.

  • Best caseO(1)

    n = 0, where the loop never runs, or a power of two, which needs one step.

  • Average caseO(k)

    One step per 1 bit, k of them. Random 32-bit values have about 16 set bits, so about 16 steps.

  • Worst caseO(k)

    Every bit set: -1 is 32 ones, so 32 steps, the most possible. The table version is O(n) for n + 1 numbers.

Common mistakes

  • Shifting a negative number right with >> in a loop like while (x) { count += x & 1; x >>= 1; }. The sign bit keeps coming back and the loop never ends. Use >>>.
  • Using n.toString(2) on a negative number. It gives "-101", not the two's complement bits. Use (n >>> 0).toString(2).
  • Counting bits of numbers above 2^32 with these operators. The high bits are dropped first; use BigInt for larger values.
  • Forgetting brackets in bits[i >> 1] + i & 1. + runs before &, so write (i & 1).

When to use it

Look for these clues in a problem:

  • The problem asks how many bits are set, how many flags are on, or how many items a mask holds.
  • You need the Hamming distance: the number of positions where two bit patterns differ, which is popcount(a ^ b).
  • You need bit counts for every number in a range.
  • Inputs are 32-bit integers, possibly negative, described in two's complement.

Check yourself

Answer each one in your head first, then open it.

How many times does the loop run for countBits(180)?

4, once per 1 bit in 10110100. The shifting version would take 8 steps and checking every position would take 32.

What does countBits(-8) return?

29. In 32-bit two's complement, -8 is 29 ones followed by three zeros.

Why can bits[i] safely use bits[i >> 1]?

i >> 1 is smaller than i, and the table is filled from small to large, so that entry is already final.

Why would while (x) { count += x & 1; x >>= 1; } never end for negative x?

>> copies the sign bit into the top, so a negative x stays negative and ends up as -1 forever. >>> brings in zeros and lets it reach 0.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

countBits keeps one promise: count plus the number of 1 bits still in x equals the answer. At the start, count is 0 and x holds all the bits, so it's true.

Each step keeps it. Subtracting 1 changes the lowest 1 of x to 0 and every 0 below it to 1; higher bits stay the same. ANDing with the old x keeps the higher bits, and clears the lowest 1 and everything below it, which were 0 in x anyway. So exactly one 1 bit disappears while count goes up by 1. When x reaches 0, no bits are left, so count is the answer, and the loop ran exactly once per 1 bit, at most 32 times.

countBitsUpTo relies on how binary numbers are built: i is i >> 1 with one more bit, i & 1, written on the end. So the count for i is the count for i >> 1 plus that last bit. Since i >> 1 is smaller than i for every i >= 1, filling the table in increasing order means the entry it needs is always ready.

Going deeper

3 more ideas

Why x & (x - 1) clears one bit

Subtracting 1 changes the lowest 1 bit to 0 and every 0 below it to 1, and leaves the higher bits alone. ANDing with the original keeps the higher bits, clears the lowest 1 bit, and clears the bits below it, which were 0 anyway. So each step removes exactly one 1 bit.

Counting for every number at once

i >> 1 drops the last bit of i, and i & 1 is that last bit. So the count for i is the count for i >> 1, which is smaller and already filled in, plus its last bit. For i = 6 (110): bits[3] + 0 = 2. The whole table takes O(n) time.

Negative numbers in JavaScript

-1 is 32 ones in two's complement, so its popcount is 32. Without >>> 0, a loop that shifts with >> would copy the sign bit forever and never reach 0. The x &= x - 1 loop still works on the signed value, but starting from n >>> 0 makes the meaning clear. Math.clz32(x) (count leading zeros) is built into JavaScript, but there is no built-in popcount.

Work it by hand

Every step in a table, with why

Count the 1 bits of 180, then fill the table of counts for 0 to 6.

countBits(180), then countBitsUpTo(6)

StepValueBinaryComputesResultWhat happensWhy
1x = 18010110100180 >>> 0count = 0start>>> 0 changes nothing for a positive number. It matters for negatives.
2x = 18010110100180 & 179176, count = 1clear lowest 1179 is 10110011: the lowest 1 (worth 4) became 0 and the two 0s below it became 1. The AND gives 10110000.
3x = 17610110000176 & 175160, count = 2clear lowest 1175 is 10101111. The AND clears the bit worth 16: 10100000.
4x = 16010100000160 & 159128, count = 3clear lowest 1159 is 10011111. Four 0 bits were skipped in one step.
5x = 12810000000128 & 1270, count = 4loop ends127 is 01111111, which shares no bit with 128. x is 0, so countBits returns 4.
6i = 11bits[0] + 11last bit is 1countBitsUpTo(6) starts with bits = [0, 0, 0, 0, 0, 0, 0]; bits[0] stays 0.
7i = 210bits[1] + 012 >> 1 is 110 is 1 with a 0 added at the end, so it has the same count as 1.
8i = 311bits[1] + 123 >> 1 is 111 is 1 with a 1 added at the end.
9i = 4100bits[2] + 014 >> 1 is 2Every power of two has a count of 1.
10i = 5101bits[2] + 125 >> 1 is 2bits[2] was filled two steps ago.
11i = 6110bits[3] + 026 >> 1 is 3The loop reaches n, so it returns the table.

countBits(180) is 4, found in 4 steps instead of 32. countBitsUpTo(6) is [0, 1, 1, 2, 1, 2, 2], with one addition per number.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Counting set bitsO(k)O(1)Counting one number's bits, especially sparse masks with only a few flags on.
Check all 32 positionsO(w)O(1)Only when you also need to visit each position, such as listing which bits are on.
Parallel counting with masksO(1)O(1)Hot code that counts millions of values; it's harder to read, so wrap it in a named function.
Table for every number up to nO(n)O(n)You need the count for every number from 0 to n, such as every subset mask.

Extra memory: O(1) for countBits: x and count. countBitsUpTo stores n + 1 counts, O(n).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Counting set bits and the other approaches, on a scale where each line up is 10 times more steps.
  • Counting set bits, Check all 32 positions, Table for every number up to n O(k)
  • Parallel counting with masks O(1)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Counting set bits101,0001 million
Check all 32 positions101,0001 million
Parallel counting with masks111
Table for every number up to n101,0001 million

Inputs that need care

5 tricky inputs
n = 0
x is 0, the loop never runs, and it returns 0. countBitsUpTo(0) returns [0].
A negative number: countBits(-8)
-8 >>> 0 is 4294967288, which is 29 ones followed by 000, so it returns 29. After the first step x becomes -16, because & returns a signed result, but the x !== 0 test still works.
countBits(-1)
All 32 bits are 1, so it returns 32 after 32 steps, the most the loop can ever take.
A number above 2^32: countBits(2 ** 32 + 7)
>>> 0 drops the high bit, so it returns 3, the count for 7. Use BigInt and x &= x - 1n for wider numbers.
A decimal: countBits(7.9)
>>> 0 cuts off the fraction, so it counts the bits of 7 and returns 3.

Variations and follow-ups

Twists interviewers add

Parallel counting

A fixed series of masks adds neighboring bits in pairs, then in groups of 4, then 8: x - ((x >>> 1) & 0x55555555), then (x & 0x33333333) + ((x >>> 2) & 0x33333333), and so on. It always takes the same few steps, with no loop, and gives the same answers as countBits.

Lookup table

Store the counts for all 256 byte values once, then add the counts of the 4 bytes of a 32-bit number: table[x & 255] + table[(x >>> 8) & 255] + .... Four lookups, whatever the number.

Hamming distance

The number of positions where two numbers differ is countBits(a ^ b), because XOR leaves a 1 exactly where they differ. For 180 and 3, 180 ^ 3 is 183 (10110111), so they differ in 6 places.

Another table rule

bits[i] = bits[i & (i - 1)] + 1 also works: i & (i - 1) is i with its lowest 1 removed, a smaller number with exactly one fewer 1 bit.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "number of 1 bits", "Hamming weight", "how many flags are set", "Hamming distance between two numbers", or "counting bits for every number up to n".
  • Explain x & (x - 1) with a small example out loud: "12 is 1100, 11 is 1011, and the AND is 1000. The lowest 1 is gone, so the loop runs once per 1 bit."
  • Test 0, a power of two, -1, and a negative number like -8. Mention why the shifting version with >> would never end for negatives.
  • The common follow-up is "counts for every number up to n in O(n)". Answer bits[i] = bits[i >> 1] + (i & 1), and explain that i >> 1 is always already filled.

Where frontend code uses it

The same idea in real UI code
  • Counting how many permissions or feature flags are on in a mask, for a badge such as "3 of 8 enabled".
  • Immutable data libraries such as Immutable.js use hash array mapped tries, which store a bitmap per node and use a popcount to find a child's position in a compact array.
  • Comparing two state masks with popcount(a ^ b) tells how many flags changed between renders or snapshots.

Related algorithms