What Is Population Count? How to Count Set Bits in Binary

Take the number 13. In binary that's 1101. Three of those four bits are 1. Count them, and you get 3. That's population count: the technical term for counting set bits in a binary integer.

Simple idea. Surprisingly rich consequences. It shows up in bitmask DP, Hamming distance questions, and any problem that models a collection of boolean flags as an integer, which is more common in interviews than you'd think until the day it bites you.

Three Names, One Idea

Population count goes by several aliases. Hamming weight is the formal term, borrowed from information theory. Engineers close to hardware call it popcount. The x86 assembly instruction is literally POPCNT. All three mean the same thing: how many 1-bits does this integer have?

Some examples to anchor the idea:

Integer	Binary	Popcount
0	`00000000`	0
1	`00000001`	1
7	`00000111`	3
13	`00001101`	3
255	`11111111`	8

Notice that 7 and 13 both have popcount 3. Popcount cares about which bit positions are set, not the numeric value.

Where Popcount Actually Shows Up

You might wonder when you'd ever need this outside a dedicated bit-manipulation problem. Turns out: often, once you start reaching for bitmasks.

Bitmask DP uses integers to represent subsets of a small set. The subset {0, 2, 3} in a 4-element universe might be encoded as 1101. Knowing how many elements are in the current subset means calling popcount on the bitmask. Held-Karp for Traveling Salesman, optimal assignment, and scheduling problems all lean on this.

Hamming distance between two integers is the popcount of their XOR. XOR flips bits wherever two values differ, and popcount counts those flips. LeetCode 461 is literally two lines once you see it: x = a ^ b, then count the 1-bits in x. LeetCode 477 scales this to arrays.

Beyond interviews: error correction protocols use Hamming weight to count how many bits flipped in transmission. Network programming uses it to count usable hosts in a subnet mask. Popcount is one of those techniques where once you know it, you start seeing it everywhere, like when you learn a new word and suddenly everyone is using it.

How to Count Set Bits: The Approach You'd Write at 2am

Inspect each bit from least significant to most significant, count the 1s.

def popcount(n: int) -> int:
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

This works. It runs in O(b) iterations where b is the bit width. For a 64-bit integer that's at most 64 iterations regardless of how many bits are set. An integer with only 2 bits set still loops 64 times, because the loop doesn't know to stop being thorough.

It's the approach you write when you understand bits well enough to not be embarrassed but not well enough to show off. Which is fine! But there's a better way.

Kernighan's Trick: Skip the Empty Bits

The key observation: n & (n - 1) clears the lowest set bit of n.

Subtracting 1 from n flips the lowest set bit to 0 and flips all trailing zeros to 1. ANDing with the original cancels those trailing 1s. The lowest set bit disappears.

Trace it with 12 (1100):

12 - 1 = 11 = 1011
12 & 11 = 1100 & 1011 = 1000 (bit at position 2 cleared)
8 - 1 = 7 = 0111
8 & 7 = 1000 & 0111 = 0000 (bit at position 3 cleared)

Two iterations, two set bits. Done.

def popcount(n: int) -> int:
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

This is the answer interviewers are hoping for when they ask you to implement popcount without built-ins. It runs in O(k) iterations where k is the number of set bits. For sparse integers, that's dramatically faster than grinding through every position. It also has the benefit of looking like you understand bits rather than understanding loops.

How CPUs Do It: Merge Counters in Parallel

This is where things get interesting if you like staring at hex masks and wondering who hurt the person who wrote this.

The approach treats the integer as a tiny array of 1-bit counters, then merges them pair by pair until one sum remains. Here it is for 32-bit integers:

def popcount(n: int) -> int:
    n = n - ((n >> 1) & 0x55555555)
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
    n = (n + (n >> 4)) & 0x0F0F0F0F
    return (n * 0x01010101) >> 24

0x55555555 in binary is 01010101..., isolating odd-positioned bits. Each step halves the number of separate counters. The final multiply collects all byte-sums in one shot, no branches anywhere. Compilers generating hardware popcount often emit similar code internally.

You don't need to derive this in an interview. Knowing it exists and why hardware popcount is cheap is enough.

One Instruction, One Clock Cycle

Modern x86 CPUs (Intel Nehalem, 2008 onward; AMD Barcelona, 2007 onward) have a POPCNT instruction that computes population count in a single clock cycle. Every major ARM chip supports the equivalent CNT. When you call a language's built-in popcount, the compiler emits this instruction directly, and everything you just read above happens in one tick of the clock.

You write the parallel bit-merging trick. The CPU has been doing it in hardware since before some of your coworkers were old enough to drive.

What to Actually Write in Code

Use the built-in. Full stop. It compiles to the hardware instruction and beats anything you'll write by hand.

Language	Built-in
Python 3.10+	`n.bit_count()`
Python (any version)	`bin(n).count('1')`
Java	`Integer.bitCount(n)` / `Long.bitCount(n)`
C++ (GCC)	`__builtin_popcount(n)` / `__builtin_popcountll(n)` for 64-bit
C++ 20	`std::popcount(n)` from `<bit>`
C (GCC)	`__builtin_popcount(n)`
Go	`bits.OnesCount(n)` from `math/bits`
Rust	`n.count_ones()`
Swift	`n.nonzeroBitCount`
Kotlin	`n.countOneBits()`
C#	`BitOperations.PopCount(n)` from `System.Numerics`
Ruby	`n.to_s(2).count('1')`
PHP	`substr_count(decbin($n), '1')`

Python's bin(n).count('1') works on any version and on arbitrarily large integers. No overflow, no need for the long variants you'd use in Java or C++. Java's Integer.bitCount handles the full 32-bit range including negative numbers, since it counts bits in the two's complement representation.

Everything Is O(1). Here's the Nuance.

For fixed-width b-bit integers:

Approach	Time	Space
Naive (shift and test)	O(b) = O(1)	O(1)
Kernighan's trick	O(k) where k = set bits = O(1)	O(1)
Parallel bit counting	O(log b) = O(1)	O(1)
Hardware POPCNT	O(1)	O(1)

All approaches are O(1) for fixed-width integers because b is a constant (32 or 64). The complexity table is a little anticlimactic: you learned four approaches and they all collapse to the same answer. But the nuance is worth stating. In an interview, give O(1) for fixed-width integers, then mention that Kernighan's approach visits only k iterations where k is the number of set bits, which matters when you expect sparse inputs. That distinction separates a competent answer from a thorough one.

If the integer is truly arbitrary precision (Python's int), the naive and Kernighan approaches become O(b) in the length of the binary representation.

Three Problems Worth Knowing Cold

LeetCode 191: Number of 1 Bits. The direct question. Most interviewers want either the bit-shifting loop or Kernighan's trick. Knowing both and explaining when each is faster shows depth. Using a built-in is fine if you can also explain the mechanism underneath.

LeetCode 338: Counting Bits. For each number from 0 to n, compute its popcount. The O(n log n) approach calls popcount naively on each number. The O(n) DP uses a recurrence: dp[i] = dp[i >> 1] + (i & 1). The popcount of i equals the popcount of i with its last bit removed, plus that last bit. Filling the table in order gives the full result in O(n) total, each step O(1).

LeetCode 461: Hamming Distance. XOR two numbers to isolate differing bits, then count those bits: diff = a ^ b, then popcount(diff). Two lines. Once you see the XOR step, the popcount falls out naturally.

The DP That Trips Candidates Up

The LeetCode 338 recurrence is elegant enough to trace through once.

def countBits(n: int) -> list[int]:
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

i >> 1 drops the least significant bit. i & 1 isolates that dropped bit. So dp[i] is the popcount of the higher bits (already computed as dp[i >> 1]) plus the lowest bit. Each step costs O(1), so the whole table fills in O(n).

This is probably the most elegant popcount application in the LeetCode catalog. Interviewers use it to separate candidates who know the obvious O(n log n) approach from those who see the DP structure underneath. It's also one of those problems where if you explain the recurrence clearly out loud, the interviewer immediately knows you actually understand it rather than memorized it.

If you want to practice explaining bit manipulation under interview pressure, SpaceComplexity runs voice-based DSA mock interviews where you work through exactly these problem types out loud and get rubric-based feedback on your reasoning.

For a full reference of bit manipulation formulas, the bit manipulation cheat sheet covers every trick in one place.