Imagine you're proofreading a document. You have two versions — the original and a revised copy. You need to count how many characters differ between them. Easy, right? Just go through line by line and tally up the differences.
Now imagine doing that for a 32,000-page document. You'd want to know exactly which positions differ and how many differences there are in total.
This is exactly what we do with binary numbers. Instead of characters, we have bits — those 0s and 1s. And instead of pages, we have integers:
Popcount = How many 1s are in this number? (Like counting typos in one document)
Hamming Distance = How many bits differ between two numbers? (Like counting differences between two documents)
Bit Flips = How many bits must change to turn A into B? (Like the editing distance between two documents)
These operations appear everywhere: error correction in networking, cryptography, chess engines (bitboards), data compression, and constantly in coding interviews. Let's master them all.
1. Popcount — Count Set Bits (Brian Kernighan's Algorithm)
The problem: Given a non-negative integer n, count how many bits are set to 1 in its binary representation.
Note
💡 Real-World Analogy: Imagine you're a teacher taking attendance in a classroom with 32 seats. Instead of calling each name one by one (checking every bit), you can just ask: "If your seat number is a power of two, raise your hand." Brian Kernighan's algorithm is like saying: "Point to the first person whose hand is up, count 1, now that person sits down. Point to the next raised hand, count 2..." You only count the students present, not the empty seats!
🤔 The Intuition — Every Bit is Either 0 or 1
Let's start simple. Take n = 12. In binary: 1100. How many 1s do you see? Two, right? That's the popcount.
But how do we make the computer count them? We have to teach it to look at each bit position. Let's explore how.
🥱 Brute Force — Check Every Bit
The most straightforward way: loop through all 32 bits (or however many bits our integer has), check each one, and increment a counter.
function popcountBrute(n) {
let count = 0;
for (let i = 0; i < 32; i++) {
if ((n >> i) & 1) count++; // Check bit at position i
}
return count;
}
// n = 12 (binary: 1100)
// i=0: 1100 & 1 = 0 → no
// i=1: 110 & 1 = 0 → no
// i=2: 11 & 1 = 1 → count=1
// i=3: 1 & 1 = 1 → count=2
// Result: 2
Key Insight
⏱ Time: O(32) = O(1) — always 32 iterations. Space: O(1). Simple, but what if the number has very few 1s? We're wasting iterations checking all those 0s!
🔍 Real-Time Thinking — What Do I Know?
"I need to count how many 1s are in a binary number. The naive way: check each of the 32 bits one by one. That works but it's 32 iterations even if the number has just one 1 bit. What if I could skip the zeros? Is there a way to say 'find the lowest 1 bit and remove it'? Hmm... what does subtracting 1 do to a binary number? It flips the lowest 1 to 0 and all zeros after it to 1. Then if I AND that with the original... the lowest 1 bit gets cleared! So n & (n-1) removes one set bit at a time. I just count how many times I can do this before n becomes 0!"
⚡ Optimal — Brian Kernighan's Algorithm
Here's the MAGIC. What if we could skip the zeros and only iterate over the 1s?
Brian Kernighan (yes, the K&R C book guy) discovered a beautiful trick:n = n & (n - 1) clears the lowest set bit. Repeat until n = 0, and count how many times you did it. That's your popcount!
📋 Edge Cases to Consider
n = 0: No set bits. The while loop never executes. Returns 0. Correct!
n = 1: One iteration of n &= n-1 clears the only bit. Returns 1.
n = 2^k (power of two): Exactly one set bit. One iteration. Returns 1.
n = all 1s (e.g., 32-bit all set): 32 iterations. Still constant time for 32-bit integers.
n is negative (JavaScript): Bitwise ops treat numbers as 32-bit signed. -1 = all 32 bits set → 32 iterations.
n = Number.MAX_SAFE_INTEGER: JavaScript truncates to 32 bits for bitwise operations. Only the lower 32 bits are processed.
function popcount(n) {
let count = 0;
while (n) {
n &= n - 1; // ← clears the lowest set bit
count++;
}
return count;
}
// n = 12 (1100)
// Iter 1: n & (n-1) = 12 & 11 = 8 (1000), count=1
// Iter 2: n & (n-1) = 8 & 7 = 0, count=2
// n = 0 → return 2 ✨
Key Insight
⏱ Time: O(number of set bits) — only iterates as many times as there are 1s! For sparse numbers, this is WAY faster. Space: O(1).
📊 Dry Run — Watch It In Action
Let's trace through popcount(12) step by step. Watch how each iteration destroys one set bit:
Iteration
n (binary)
n-1 (binary)
n & n-1
Count
What Happened?
Start
12 (1100)
—
—
0
Initial state
1
12 (1100)
11 (1011)
8 (1000)
1
Lowest set bit (position 2) cleared! 🔥
2
8 (1000)
7 (0111)
0 (0000)
2
Next set bit cleared! n=0 → done ✅
🔍 Why Does n & (n-1) Work?
Let's really understand this. Not just memorize it.
When you subtract 1 from a number:
The lowest 1 bit becomes 0. Think of it like borrowing in subtraction.
All bits to the right (trailing zeros) become 1.
Then when you AND the original with this result, the changed region (the lowest 1 → 0 and all trailing 0s → 1) becomes 0. Everything above stays the same.
// Visual proof: n = 12
n = 1100 (binary)
n-1 = 1011 (subtract 1: lowest 1→0, trailing 0s→1)
-------------------
& = 1000 (only the unchanged upper bits survive)
// n = 8 (after first iteration)
n = 1000
n-1 = 0111 (lowest 1→0, all three trailing 0s→1)
-------------------
& = 0000 (nothing left!)
Tip
💡 Pro Tip: This trick isn't just for popcount. n & (n-1)is a superpower — use it to check if n is a power of 2 (single set bit → clears to 0), to iterate over subsets, and more!
Edge Cases
n = 0 → while loop never runs → count = 0. Correct!
n = 1 (binary: 1) → one iteration → count = 1. Correct!
n = 2³²-1 (all 32 bits set) → 32 iterations. Still constant time!
n = 2^k (power of two, e.g., 8 = 1000) → exactly 1 iteration. Fast!
Negative numbers? In JavaScript, bitwise operators work on 32-bit signed integers. Two's complement means -1 (all 32 bits = 1) → 32 iterations.
PROBLEMNumber of 1 Bits
Write a function that takes a non-negative integer n and returns the number of '1' bits (popcount). Implement Kernighan's algorithm.
Loading playground...
Note
🔮 Extending the pattern:n & (n-1) has more uses: checking if n is a power of 2 (n > 0 && (n & (n-1)) === 0), and finding the next lower number with fewer set bits. This one operation is a Swiss Army knife!
2. Counting Bits — The DP Pattern
Problem: Given an integer n, return an array ans of lengthn + 1 where ans[i] is the popcount of i.
Wait — can't we just call our popcount function for each i from 0 to n? Yes! But that's O(n log n). There's a beautiful DP recurrence that makes it O(n).
🤔 The Intuition — Removing the LSB
Here's the key insight: every integer i is related to a smaller integer.
i >> 1 (right-shift by 1) removes the least significant bit (LSB). So popcount(i) = popcount(i >> 1) + (i & 1).
In English: "The popcount of i is the popcount of i without its last bit, plus 1 if that last bit was a 1."
Since i >> 1 < i, we've already computed its popcount earlier in the loop. It's a linear DP with O(1) per step!
🤔 The Decision: Right-Shift or Not?
Here's the key question for each number i: "Do I compute popcount from scratch, or do I reuse the answer for a smaller number?" If I right-shift i by 1 (i >> 1), I get a smaller number whose popcount I already computed. The only thing I lose is the LSB. So I either choose to reuse the known popcount of i>>1 and add (i & 1) for the LSB, or I choose to compute from scratch (which is wasteful). The DP approach chooses reuse — O(1) per number instead of O(32).
⏱ Time: O(n), Space: O(n). We compute all popcounts in one linear pass. Each step is just a right-shift, an AND, and an addition. Blazing fast!
📊 Dry Run — DP Table for 0 to 15
Let's see the recurrence in action. The highlighted row (i=5) shows how dp[5] = dp[2] + 1:
Do you see the pattern? Every even number has the same popcount as n/2 (right-shift just drops a 0). Every odd number has popcount = popcount(n/2) + 1 (right-shift drops a 1, so we add it back).
🔄 Alternative: DP with LSB Reset
There's another recurrence using Kernighan's trick:
function countBits(n) {
const dp = [0];
for (let i = 1; i <= n; i++) {
dp[i] = dp[i & (i - 1)] + 1;
// ^^^^^^^^^^^^^^^ ^^^
// popcount of i add back the
// without lowest cleared bit
// set bit
}
return dp;
}
Same O(n) time. Use whichever recurrence clicks for you.
Large n (e.g., 10⁵) → still O(n). The array just grows.
n = 2^k - 1 (all ones, e.g., 7 = 111) → dp[i] = number of bits = log₂(i+1).
PROBLEMCounting Bits
Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1's in the binary representation of i. Use the DP recurrence for O(n) time.
Loading playground...
3. Hamming Distance — Number of Differences
Problem: Given two integers x and y, count how many positions have different bits.
Note
🔍 Real-World Analogy: Imagine you and a friend each have a row of 32 light switches. You want to count how many switches are in different positions. Instead of checking each switch one by one (comparing position 0, then 1, then 2...), you can XOR the two rows — any switch that's different lights up as 1. Then count the lit switches with popcount! XOR finds the differences, popcount counts them. Two operations, done. 🎯
Wait a second — do you see what we need? We need to find where bits DIFFER. And what bitwise operation tells us where bits differ?
That's right — XOR! ⊕
🤔 The Intuition — XOR + Popcount = 🧠
Remember the XOR article? XOR produces 1 exactly where bits differ. So:
Hamming Distance = popcount(x ⊕ y)
That's it. Two operations. One line of code. Beautiful.
📐 The Formula
function hammingDistance(x, y) {
return popcount(x ^ y);
}
// Let's trace: x=5 (0101), y=3 (0011)
// x ^ y = 0101 ^ 0011 = 0110 (binary 6)
// popcount(0110) = 2
// So 2 bits differ between 5 and 3!
🔍 Why XOR + Popcount?
XOR at the bit level is "different = 1, same = 0". When we XOR x and y, every 1 in the result marks a position where x and y differ.
So counting those 1s (popcount) gives us the exact count of differing positions. It's the fastest Hamming distance possible: XOR is one CPU instruction, POPCNT is another. Two instructions total!
Tip
⚡ Interview Tip: When asked "how many bits differ between two numbers?" — your brain should instantly fire: "XOR followed by popcount!"
🚀 Total Hamming Distance — The O(n) Trick
Advanced Problem: Given an array of integers, find the sum of Hamming distances between ALL pairs.
Brute force: O(n²) — compute Hamming distance for each of the n(n-1)/2 pairs. But there's an O(n) solution that's pure genius.
function totalHammingDistance(nums) {
let total = 0;
const n = nums.length;
// Check each of the 32 bit positions
for (let bit = 0; bit < 32; bit++) {
let ones = 0;
// Count how many numbers have this bit set
for (const num of nums) {
if ((num >> bit) & 1) ones++;
}
const zeros = n - ones;
// Each (1,0) pair contributes 1 to the total
total += ones * zeros;
}
return total;
}
// Array: [4, 14, 2]
// Bit position 0: ones=1 (14), zeros=2 → 1×2 = 2
// Bit position 1: ones=2 (14,2), zeros=1 → 2×1 = 2
// Bit position 2: ones=2 (4,14), zeros=1 → 2×1 = 2
// Bit position 3: ones=1 (14), zeros=2 → 1×2 = 2
// Total = 2+2+2+2 = 8
Key Insight
🔑 The Insight: Instead of comparing pairs directly, we count per bit position. At each bit, every 1-0 pair adds 1 to the total. There are exactly ones × zeros such pairs. Sum across all 32 bits. O(32n) = O(n)!
Edge Cases
x = y → x ⊕ y = 0 → popcount = 0. No differences.
x = 0 → popcount(y) = Hamming distance. Just count set bits of y.
Large numbers → XOR works on all 32 bits, fine.
Total, single element → no pairs, total = 0.
Total, all same → every bit position: ones = n or 0 → ones × zeros = 0. Correct!
PROBLEMHamming Distance
Given two integers x and y, return the Hamming distance between them — the number of positions where their bits differ. Use popcount(x ^ y).
Loading playground...
PROBLEMTotal Hamming Distance
Given an integer array nums, return the sum of Hamming distances between all pairs. Solve in O(n) by counting per-bit contributions.
Loading playground...
4. Reverse Bits — Divide & Conquer
Problem: Reverse the bits of a 32-bit unsigned integer. If the input is1 (binary: 00000000000000000000000000000001), the output should be 2147483648(10000000000000000000000000000000).
🔍 Real-Time Thinking — What Do I Know?
"I need to reverse 32 bits. The brute force: loop through 32 bits, extract each bit, place it in the reversed position. That's O(32) — fine, but can I do better? What if I treat this like a sorting network? First swap the two 16-bit halves. Then within each 16-bit half, swap the 8-bit quarters. Then 4-bit nibbles, then 2-bit pairs, then adjacent bits. That's just 5 operations! Each swap is just a shift and mask. Let me think about the masks I need..."
🤔 The Intuition — Swapping at Every Scale
The naive approach: loop through 32 bits, build the result bit by bit. Works, O(32), fine.
But there's a more elegant way — divide and conquer. Instead of reversing one bit at a time, we reverse at increasingly fine granularity:
Swap the 16-bit halves
Swap the 8-bit halves within each 16-bit chunk
Swap the 4-bit halves within each 8-bit chunk
Swap the 2-bit halves within each 4-bit chunk
Swap adjacent bits (1-bit halves)
Five operations. That's it. The whole 32-bit number is reversed.
n = 2³²-1 (all 1s) → every swap keeps all 1s → returns same value.
n with alternating bits (0xAAAAAAAA) → after step 5, becomes 0x55555555.
Unsigned result — JavaScript's {>>> 0 converts to unsigned 32-bit.
PROBLEMReverse Bits
Reverse bits of a given 32-bit unsigned integer using divide and conquer. Swap halves at decreasing scales: 16, 8, 4, 2, 1.
Loading playground...
5. Bit Flips — Minimum Changes
Problem: How many bits do we need to flip (0→1 or 1→0) to convert one integer into another?
🤔 The Intuition — Same as Hamming Distance!
Wait a moment... "convert a to b" — that means changing the bits that differ. And we already know how to find differing bits!
Minimum Bit Flips = popcount(start ⊕ goal)
Yes! It's the exact same formula as Hamming Distance! Every differing bit needs exactly one flip. XOR finds the differences, popcount counts them.
📐 The Algorithm
function minBitFlips(start, goal) {
return popcount(start ^ goal);
}
// a = 10 (1010), b = 7 (0111)
// a ^ b = 1010 ^ 0111 = 1101
// popcount(1101) = 3
// Need to flip 3 bits!
🔍 Visual Breakdown
Let's see exactly which bits flip:
Bit Position
a = 10
b = 7
Flip Needed?
3 (MSB)
1
0
Yes — 1 → 0
2
0
1
Yes — 0 → 1
1
1
1
No (same)
0 (LSB)
0
1
Yes — 0 → 1
Three positions differ → three flips needed. popcount(10 ^ 7) = popcount(13) = 3. Confirmed! ✅
🔢 Prime Number of Set Bits
Follow-up: Given a range [left, right], count how many numbers have aprime number of set bits in their binary representation.
This combines popcount with primality testing:
Compute popcount for each number in the range
Check if the popcount is a prime number (2, 3, 5, 7, 11, 13, 17, 19...)
Since numbers are ≤ 10⁶, popcount is at most 20 — precompute primes up to 20!
function countPrimeSetBits(left, right) {
// Primes up to 20 (max popcount for 10^6)
const primes = new Set([2, 3, 5, 7, 11, 13, 17, 19]);
let count = 0;
for (let i = left; i <= right; i++) {
// Compute popcount
let n = i, bits = 0;
while (n) { n &= n - 1; bits++; }
if (primes.has(bits)) count++;
}
return count;
}
Prime set bits, single number → check popcount of that number.
PROBLEMMinimum Bit Flips to Convert Number
A bit flip changes a bit from 0 to 1 or 1 to 0. Given two integers start and goal, return the minimum number of bit flips to convert start to goal.
Loading playground...
PROBLEMPrime Number of Set Bits
Given two integers left and right, return the count of numbers in the inclusive range [left, right] having a prime number of set bits in their binary representation.
Loading playground...
6. Sort by Set Bits — Custom Comparator
Problem: Sort an integer array by the number of 1 bits in each element. If two numbers have the same popcount, sort by their integer value.
🤔 The Intuition — Popcount as a Sort Key
This is beautifully straightforward once you know popcount. Just compute it for each element and use it as a sorting key. Ties are broken by the element's value.
If the array is very large, calling popcount for each comparison can be expensive. Precompute popcounts using the DP recurrence:
function sortByBits(arr) {
// Precompute popcounts up to max value
const maxVal = Math.max(...arr);
const pop = new Array(maxVal + 1).fill(0);
for (let i = 1; i <= maxVal; i++) {
pop[i] = pop[i >> 1] + (i & 1);
}
return arr.sort((a, b) => {
if (pop[a] !== pop[b]) return pop[a] - pop[b];
return a - b;
});
}
Key Insight
⏱ Time: O(n log n + maxVal), Space: O(maxVal). We trade memory for speed. The DP precomputation is O(maxVal) and then each comparison is O(1) popcount lookup.
Edge Cases
Empty array → returns []. Nothing to sort.
Single element → returns the same array.
All same value → all have same popcount → sorted by value (no change if all equal).
Negative numbers → In JavaScript, bitwise ops treat them as 32-bit signed. -1 has all 32 bits set → popcount = 32.
PROBLEMSort Integers by The Number of 1 Bits
Given an integer array arr, sort the integers in ascending order by the number of 1's in their binary representation. Ties are broken by ascending integer value.
Loading playground...
🎯 Interview Cheat Sheet — Bit Counting & Hamming Distance
Key Insight
Q1: How do you count set bits (popcount) without built-in functions? Use Kernighan's algorithm: while (n) { n &= n - 1; count++; }. Each iteration clears one set bit. O(number of set bits). For sparse numbers, this is much faster than checking all 32 bits.
Key Insight
Q2: What's the DP recurrence for Counting Bits (LeetCode 338)? dp[i] = dp[i >> 1] + (i & 1). Right-shift removes the LSB;dp[i >> 1] is already computed because it's a smaller number; add back(i & 1) for the removed LSB. Builds the entire array in O(n).
Key Insight
Q3: What's the formula for Hamming Distance? popcount(x ^ y). XOR produces 1 exactly where bits differ. Popcount counts those 1s. Two operations, O(1) on modern hardware (XOR + POPCNT are single CPU instructions).
Key Insight
Q4: How do you sum Hamming distances across all pairs in O(n)? For each bit position (0 to 31), count how many numbers have that bit set (ones). Pairs that differ at this bit = ones * (n - ones). Sum across all 32 positions. O(32n) = O(n). Much faster than comparing all n² pairs!
Key Insight
Q5: How do you reverse 32 bits efficiently? Divide and conquer: swap 16-bit halves, then 8-bit halves, then 4-bit, 2-bit, 1-bit. Five bitwise operations using masks. O(1) time. No loops needed.
Key Insight
Q6: How many bit flips to convert number A to B? popcount(A ^ B). Every differing bit needs exactly one flip. XOR finds where they differ, popcount counts the flips needed.
Key Insight
Q7: What's the fastest way to check if a number has exactly one set bit? n > 0 && (n & (n - 1)) === 0. Our Kernighan trick clears the only set bit → result is 0. This is the classic "power of two" check!
Key Insight
Q8: Can I use built-in popcount in production? Modern JS engines don't have a native popcount. Use n.toString(2).replace(/0/g, '').lengthor the bitwise implementation. In C++/Rust, use __builtin_popcount or.count_ones(). In Python, n.bit_count() (Python 3.8+).
📝 Key Takeaways
Popcount via Kernighan's algorithm — n & (n-1) clears the lowest set bit. Iterates once per 1 bit, not per total bit.
Counting Bits DP — dp[i] = dp[i >> 1] + (i & 1). Computes popcounts for 0..n in O(n) time. A beautiful linear DP.
Total Hamming Distance — Count per-bit contributions: ones × zeros at each position, summed across 32 bits. O(n).
Reverse Bits — Divide and conquer: swap 16, 8, 4, 2, 1 bit halves. Five operations, O(1).
Minimum Bit Flips — popcount(start ^ goal). Same as Hamming distance! Each differing bit needs one flip.
Sort by Set Bits — Use a custom comparator keyed on (popcount(x), x). Precompute via DP for large arrays.
The core insight — XOR is the "difference detector." Combined with popcount, it solves Hamming distance, bit flips, and comparison problems. n & (n-1) is the "lowest set bit remover." Combined with a counter, it solves popcount.
Note
🔮 What's Next? You've mastered counting bits and measuring distances. Now head over to Power Detection & Binary Propertiesto learn how to check if a number is a power of two (or four, or three), Gray code, and integer replacement!