Counting & checking bits
In one line
x & (x - 1) clears the lowest set bit, which gives a fast way to count 1 bits, test for powers of two and reuse earlier answers to count bits for every number up to n.
What it is
Counting bits means finding how many 1s are in an integer's binary form, also called its population count or Hamming weight. 12 is 1100, so its count is 2.
The key trick is x & (x - 1). Subtracting 1 turns the lowest 1 bit into 0 and every 0 below it into 1. ANDing with the original then removes that lowest 1 and leaves all higher bits untouched. For 12: 1100 & 1011 = 1000. Related checks include whether a number is a power of two (exactly one set bit) and the Hamming distance between two numbers (the count of bits where they differ).
Why interviewers ask
Questions like Number of 1 Bits, Power of Two, Counting Bits and Hamming Distance are common warm-ups. They test whether you know the x & (x - 1) trick, can explain why it works, and can spot the DP relation for counting bits of all numbers up to n in O(n) instead of O(n log n).
How it works
- 1Simple count: check bit 0 with x & 1, shift right, repeat until x is 0. This takes one step per bit position, about 32 for a 32-bit number.
- 2Brian Kernighan's count: repeat x = x & (x - 1) and add 1 each time until x is 0. It loops once per set bit, so sparse numbers finish fast.
- 3Power of two: a positive number is a power of two when it has exactly one set bit, which means x > 0 and x & (x - 1) == 0.
- 4Counting bits for all i from 0 to n: i >> 1 drops the last bit and is smaller than i, so bits[i] = bits[i >> 1] + (i & 1). Fill the array left to right.
- 5Hamming distance between a and b: a ^ b has a 1 exactly where they differ, so count the bits of a ^ b. In Python 3.10+, int.bit_count() does the count for you, and most CPUs have a POPCNT instruction.
Worked example · Kernighan's loop on 44, then bits[0..6]
- 44 is 101100. Step 1: 101100 & 101011 = 101000 (40), count = 1.
- Step 2: 101000 & 100111 = 100000 (32), count = 2.
- Step 3: 100000 & 011111 = 000000, count = 3. The loop ran 3 times for 3 set bits, not 6 times for 6 positions.
- Now bits for 0 to 6. bits[0] = 0. bits[1] = bits[0] + 1 = 1. bits[2] = bits[1] + 0 = 1. bits[3] = bits[1] + 1 = 2.
- bits[4] = bits[2] + 0 = 1. bits[5] = bits[2] + 1 = 2. bits[6] = bits[3] + 0 = 2. Result [0, 1, 1, 2, 1, 2, 2].
Picture it
Counting set bits with Kernighan's trick is like counting people in a row of seats by asking the first seated person to leave, again and again, until the row is empty. You only spend time on the occupied seats, not on every seat in the hall.
Reference code
def popcount(x):
# Brian Kernighan: each step clears the lowest set bit
count = 0
while x:
x &= x - 1
count += 1
return count
def is_power_of_two(x):
return x > 0 and x & (x - 1) == 0
def count_bits_upto(n):
# bits[i] = number of 1s in i, for every i in 0..n, in O(n)
bits = [0] * (n + 1)
for i in range(1, n + 1):
bits[i] = bits[i >> 1] + (i & 1)
return bits
def hamming_distance(a, b):
return popcount(a ^ b)
print(popcount(12), (12).bit_count()) # 2 2 (bit_count needs Python 3.10+)
print(is_power_of_two(64), is_power_of_two(0), is_power_of_two(12)) # True False False
print(count_bits_upto(6)) # [0, 1, 1, 2, 1, 2, 2]
print(hamming_distance(1, 4)) # 2
popcount runs once per set bit. is_power_of_two needs the x > 0 guard because 0 & -1 is 0. count_bits_upto reuses the answer for i >> 1, which is already computed because it is smaller than i.
Key patterns
Clear lowest set bit
When: Counting bits, or looping over set bits one by one
How: x &= x - 1 removes the lowest 1. Combine with x & -x to get that bit's value before removing it.
Power of two (and four)
When: Checking sizes, alignments or exact powers
How: x > 0 and x & (x - 1) == 0. For power of four also require the bit at an even position: x & 0x55555555 != 0.
DP over bit counts
When: Need the count for every number 0..n
How: bits[i] = bits[i >> 1] + (i & 1), or bits[i] = bits[i & (i - 1)] + 1. O(n) total.
Hamming distance
When: Comparing fingerprints or binary codes
How: popcount(a ^ b). For many pairs, sum per-bit: count of ones c at each position contributes c * (n - c).
Real-world use
Near-duplicate detection with SimHash
Google described using SimHash to find near-duplicate web pages: each page gets a 64-bit fingerprint, and two pages are near-duplicates when the Hamming distance (popcount of the XOR) is at most a few bits.
Redis BITCOUNT
Redis BITCOUNT counts set bits in a bitmap, such as counting how many users were active today when each user is one bit, using fast popcount over the stored bytes.
Image similarity hashes
Perceptual hashes (such as pHash or dHash) turn an image into a 64-bit fingerprint, and photo tools compare images by the Hamming distance between fingerprints.
Error detection with parity
A parity bit is the count of 1 bits modulo 2. Memory and serial links use parity, and error-correcting codes like Hamming codes build on the same counting idea to locate a flipped bit.
In a project
You run a photo-sharing app with 5 million uploads and want to flag reposts of the same picture even after resizing or recompression.
- Compute a 64-bit perceptual hash (for example dHash) for each image at upload time and store it as an integer column.
- For a new upload, compute its hash and compare to candidates with popcount(new ^ old).
- Treat distance at most 6 as a likely duplicate, and tune the threshold on a labelled sample.
- To avoid comparing against all 5 million, split each hash into 4 blocks of 16 bits and index by block: two hashes within distance 3 must match exactly on at least one block.
Impact: Each comparison is one XOR and one popcount, a few nanoseconds, so checks stay fast at upload time. Duplicate reposts are caught automatically, reducing manual moderation work.
Trade-offs
Use it when
- Counting or iterating over set bits, especially when few are set
- Checking powers of two for sizes, alignment or capacity
- Comparing binary fingerprints by Hamming distance
Avoid it when
- A built-in (int.bit_count, Integer.bitCount, __builtin_popcount) is allowed; it is clearer and uses the CPU instruction
- Negative numbers in Python with the loop version: they have infinitely many sign bits, so mask to 32 bits first
- Readability matters more than micro speed in business code
Cost: Shift-by-one count: O(number of bits). Kernighan: O(number of set bits). Counting bits for 0..n: O(n) time and space. Power of two check: O(1).
Common mistakes
- Forgetting x > 0 in the power-of-two check, so 0 is reported as a power of two.
- Running the popcount loop on a negative Python integer, which never ends because x never reaches 0; mask with 0xFFFFFFFF first.
- Writing x & x - 1 == 0 without parentheses; in Python == binds tighter than &, so it becomes x & ((x - 1) == 0).
- Using bin(x).count('1') and calling it O(1); it is O(number of bits) and builds a string.
- Missing the O(n) DP for counting bits and giving the O(n log n) per-number answer.
Interview questions
Quick revision
- x & (x - 1) clears the lowest set bit.
- x & -x isolates the lowest set bit.
- Kernighan popcount loops once per 1 bit.
- Power of two: x > 0 and (x & (x - 1)) == 0.
- bits[i] = bits[i >> 1] + (i & 1), O(n) for all 0..n.
- Hamming distance = popcount(a ^ b).
- Python 3.10+: x.bit_count(); Java: Integer.bitCount(x).
Check yourself
1. What does x & (x - 1) do?
2. Using bits[i] = bits[i >> 1] + (i & 1), what is bits[6]?
3. What is the Hamming distance between 1 and 4?
4. Why does the check x & (x - 1) == 0 need x > 0 as well?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.