Brian Kernighan's Algorithm / Popcount (n & (n-1))
Given a positive integer n, count how many bits equal 1 appear in its binary form — this count is known as the number's Hamming weight.
A set bit refers to a bit in the binary representation of a number that is equal to 1.
n = 11 is 1011 in binary, which contains three 1-bits.Kernighan's Bit Trick
number ➔ lowest set bit ➔ one fewer bit| 1 | def count_set_bits(n: int) -> int: |
| 2 | """Number of 1 Bits: counts the 1s with Brian Kernighan's trick. |
| 3 | Time: O(K), K = number of set bits (<= 32) | Space: O(1) |
| 4 | """ |
| 5 | count = 0 |
| 6 | while n > 0: |
| 7 | n &= (n - 1) # Clear lowest set bit |
| 8 | count += 1 |
| 9 | return count |
| 10 | |
| 11 | def is_power_of_two(n: int) -> bool: |
| 12 | """Power of Two: exactly one set bit, and n must be positive. |
| 13 | Time: O(1) | Space: O(1) |
| 14 | """ |
| 15 | return n > 0 and (n & (n - 1)) == 0 # n > 0 is mandatory: 0 & -1 == 0 |
n &= (n - 1) removes exactly one set bit, so count plus the set bits still in n always equals the set bits of the original n.n & (n - 1) clears the lowest set bit of n, so count_set_bits repeats it and counts the rounds until n is 0. Subtracting 1 turns the lowest 1 into 0 and every 0 below it into 1, while the higher bits stay the same, so the AND keeps exactly the higher bits: each round removes one set bit, and the loop runs once per set bit. The same fact makes is_power_of_two one test, since a power of two has exactly one set bit. The trap is n = 0: while n > 0 stops there because no set bit is left to clear, but 0 & -1 is also 0, so is_power_of_two needs the same n > 0 guard, or is_power_of_two(0) returns True.
See it run
Kernighan's Bit Trick, step by step
n 1011count 0
Each column is one bit position. The rows are n, n - 1, and n & (n - 1).
low 1the lowest set bit of nflippedthe bits of n - 1 that differ from nclearedthe bit that n & (n - 1) removed
Start: n = 1011 (11) and count = 0. The loop runs while n > 0.
Gotcha 1 of 3
- The trap
Gotcha 1: Testing a power of two without
n > 0Mistakereturn (n & (n - 1)) == 0Fixreturn n > 0 and (n & (n - 1)) == 0What happens: A power of two has exactly one set bit, so
n & (n - 1)clears it and leaves 0. But 0 has no set bit, and0 & -1is also 0. So the test alone calls 0 a power of two. The guardn > 0rules it out.Example: n = 0Mistake: returns TrueFix: returns False
- Every bit must move to a new position, as in Reverse Bits (LC 190), not just be counted or tested. See Bit Tricks
Deep Dive
Why n & (n - 1) clears the lowest set bit
Write n in binary as a prefix, then a lowest 1, then zeros: prefix 1 000. Subtracting 1 borrows from that lowest 1. It becomes 0, and every 0 below it becomes 1. The prefix does not change: prefix 0 111.
The AND of the two numbers keeps a bit only where both have a 1. The prefix is in both, so it stays. The position of the lowest 1 is 1 in n and 0 in n - 1, so it is cleared. The zeros below are 0 in n, so they stay 0.
Example: n = 12 is 1100 and n - 1 = 11 is 1011. The AND is 1000, which is 8. Exactly one set bit was removed.
Counting set bits: the loop runs once per set bit
count_set_bits repeats n &= (n - 1) and adds 1 to count each time. Each round removes one set bit, so the invariant holds: count plus the set bits still in n equals the set bits of the original n. When n is 0, no set bit is left, and count is the answer.
The cost is O(K) where K is the number of set bits. For n = 11 (1011) the loop runs 3 times, and for n = 2**30 it runs once. Checking every position would always take 32 rounds.
The loop condition is n > 0. It is correct for non-negative numbers. See the last section for negative values.
Power of two and the same trick for tests
A power of two has exactly one set bit. After one round of n & (n - 1), that bit is gone and the result is 0. So is_power_of_two is n > 0 and (n & (n - 1)) == 0.
The guard n > 0 is required. The number 0 has no set bit, but 0 & -1 is also 0, so the test alone calls 0 a power of two. A negative number is not a power of two either, and the guard rejects it.
For Power of Four (LC 342), add one more fact: the single set bit must be at an even position. The mask 0x55555555 has 1s at the even positions, so the extra test is n & 0x55555555 != 0.
Reuse: counting bits for every number up to n
Because i & (i - 1) is i with one set bit removed, it is a smaller number that was already computed. For Counting Bits (LC 338), write dp[i] = dp[i & (i - 1)] + 1. Each answer takes O(1) time, so all of 0..n costs O(n).
Example: dp[0..8] is [0, 1, 1, 2, 1, 2, 2, 3, 1]. For i = 6 (110), 6 & 5 = 4, dp[4] = 1, so dp[6] = 2.
Negative values need care. A negative Python integer has no fixed width, so while n > 0 ends at once and returns 0. When a problem gives a 32-bit value as a signed integer, use n & 0xFFFFFFFF first. For -1 the result is 32 set bits.
60-Second Pitch
"The simple way to count set bits tests all 32 positions. I use n & (n - 1) instead. Subtracting 1 turns the lowest 1 into 0 and the zeros below it into 1s, so the AND clears exactly the lowest set bit. The loop runs once per set bit, so the time is O(K) with K at most 32, and the space is O(1). The same fact tests a power of two in one line, n > 0 and (n & (n - 1)) == 0. I keep the n > 0 guard, because zero would otherwise pass. For a signed 32-bit input, I mask with 0xFFFFFFFF first."
Common Questions
- Why does
n & (n - 1)remove exactly one set bit? Subtracting 1 flips the lowest set bit to 0 and every lower zero to 1. The bits above stay the same. The AND keeps the higher bits and clears the lowest set bit and the bits below. For
12 & 11,1100 & 1011gives1000.- What is the time complexity of
count_set_bits, and how does it compare with a loop over 32 bits? It is O(K), where K is the number of set bits, at most 32. The loop over all positions always takes 32 rounds. For a sparse value such as
2**30, Kernighan's version takes 1 round.- How do you test for a power of two, and why is
n > 0needed? Use
n > 0 and (n & (n - 1)) == 0. A power of two has one set bit, so one clear step gives 0. The number 0 also gives 0 after the step, so withoutn > 0it would be accepted. Negative numbers are rejected by the same guard.- How do you handle a negative input in Python?
A negative Python integer has no fixed width, so
while n > 0returns 0 at once. If the problem means a 32-bit value, applyn & 0xFFFFFFFFfirst. For-1, the count is then 32.- How does the trick give all bit counts from 0 to n in
O(n)? i & (i - 1)isiwith its lowest set bit removed, a smaller number. Sodp[i] = dp[i & (i - 1)] + 1. Each value takesO(1)time, as in Counting Bits (LC 338).
SWE Reasoning
Spot it
- The problem asks for the number of 1 bits (Number of 1 Bits (LC 191), Hamming weight).
- The problem asks whether a number is a power of two, or a power of four (Power of Two (LC 231), Power of Four (LC 342)).
- The loop must visit only the set bits of a mask, not all 32 positions.
- The answer for a number can be built from the answer for the same number with one set bit removed (Counting Bits (LC 338)).
The invariant, step by step
countis 0 andnholds the input.- While
n > 0,nhas at least one set bit. n &= (n - 1)clears the lowest set bit and changes nothing else.count += 1records that one set bit was removed.- So at every step,
countplus the set bits still innequals the set bits of the originaln. - When
nreaches 0, no set bit is left, andcountequals the set bits of the originaln.
Traps
- Power of two without
n > 0.is_power_of_two(0)returnsTrue, because0 & -1is 0. Add the guard. - Shifting instead of clearing.
n >>= 1removes the lowest bit whether it is 0 or 1. Ifcountstill grows each round, it counts the length ofnin bits.count_set_bits(11)returns 4 instead of 3. - Negative input.
while n > 0stops at once for a negative Python integer and returns 0. Usen & 0xFFFFFFFFfor a 32-bit signed value. - Power of four with only the one-bit test.
8has one set bit but is not a power of four. Also check the position with0x55555555.
Practice
Brian Kernighan's Algorithm / Popcount (n & (n-1))
Given a positive integer n, count how many bits equal 1 appear in its binary form — this count is known as the number's Hamming weight.
A set bit refers to a bit in the binary representation of a number that is equal to 1.
n = 11 is 1011 in binary, which contains three 1-bits.Kernighan's Bit Trick
number ➔ lowest set bit ➔ one fewer bit| 1 | def count_set_bits(n: int) -> int: |
| 2 | """Number of 1 Bits: counts the 1s with Brian Kernighan's trick. |
| 3 | Time: O(K), K = number of set bits (<= 32) | Space: O(1) |
| 4 | """ |
| 5 | count = 0 |
| 6 | while n > 0: |
| 7 | n &= (n - 1) # Clear lowest set bit |
| 8 | count += 1 |
| 9 | return count |
| 10 | |
| 11 | def is_power_of_two(n: int) -> bool: |
| 12 | """Power of Two: exactly one set bit, and n must be positive. |
| 13 | Time: O(1) | Space: O(1) |
| 14 | """ |
| 15 | return n > 0 and (n & (n - 1)) == 0 # n > 0 is mandatory: 0 & -1 == 0 |
n &= (n - 1) removes exactly one set bit, so count plus the set bits still in n always equals the set bits of the original n.n & (n - 1) clears the lowest set bit of n, so count_set_bits repeats it and counts the rounds until n is 0. Subtracting 1 turns the lowest 1 into 0 and every 0 below it into 1, while the higher bits stay the same, so the AND keeps exactly the higher bits: each round removes one set bit, and the loop runs once per set bit. The same fact makes is_power_of_two one test, since a power of two has exactly one set bit. The trap is n = 0: while n > 0 stops there because no set bit is left to clear, but 0 & -1 is also 0, so is_power_of_two needs the same n > 0 guard, or is_power_of_two(0) returns True.
See it run
Kernighan's Bit Trick, step by step
n 1011count 0
Each column is one bit position. The rows are n, n - 1, and n & (n - 1).
low 1the lowest set bit of nflippedthe bits of n - 1 that differ from nclearedthe bit that n & (n - 1) removed
Start: n = 1011 (11) and count = 0. The loop runs while n > 0.
Gotcha 1 of 3
- The trap
Gotcha 1: Testing a power of two without
n > 0Mistakereturn (n & (n - 1)) == 0Fixreturn n > 0 and (n & (n - 1)) == 0What happens: A power of two has exactly one set bit, so
n & (n - 1)clears it and leaves 0. But 0 has no set bit, and0 & -1is also 0. So the test alone calls 0 a power of two. The guardn > 0rules it out.Example: n = 0Mistake: returns TrueFix: returns False
- Every bit must move to a new position, as in Reverse Bits (LC 190), not just be counted or tested. See Bit Tricks
Deep Dive
Why n & (n - 1) clears the lowest set bit
Write n in binary as a prefix, then a lowest 1, then zeros: prefix 1 000. Subtracting 1 borrows from that lowest 1. It becomes 0, and every 0 below it becomes 1. The prefix does not change: prefix 0 111.
The AND of the two numbers keeps a bit only where both have a 1. The prefix is in both, so it stays. The position of the lowest 1 is 1 in n and 0 in n - 1, so it is cleared. The zeros below are 0 in n, so they stay 0.
Example: n = 12 is 1100 and n - 1 = 11 is 1011. The AND is 1000, which is 8. Exactly one set bit was removed.
Counting set bits: the loop runs once per set bit
count_set_bits repeats n &= (n - 1) and adds 1 to count each time. Each round removes one set bit, so the invariant holds: count plus the set bits still in n equals the set bits of the original n. When n is 0, no set bit is left, and count is the answer.
The cost is O(K) where K is the number of set bits. For n = 11 (1011) the loop runs 3 times, and for n = 2**30 it runs once. Checking every position would always take 32 rounds.
The loop condition is n > 0. It is correct for non-negative numbers. See the last section for negative values.
Power of two and the same trick for tests
A power of two has exactly one set bit. After one round of n & (n - 1), that bit is gone and the result is 0. So is_power_of_two is n > 0 and (n & (n - 1)) == 0.
The guard n > 0 is required. The number 0 has no set bit, but 0 & -1 is also 0, so the test alone calls 0 a power of two. A negative number is not a power of two either, and the guard rejects it.
For Power of Four (LC 342), add one more fact: the single set bit must be at an even position. The mask 0x55555555 has 1s at the even positions, so the extra test is n & 0x55555555 != 0.
Reuse: counting bits for every number up to n
Because i & (i - 1) is i with one set bit removed, it is a smaller number that was already computed. For Counting Bits (LC 338), write dp[i] = dp[i & (i - 1)] + 1. Each answer takes O(1) time, so all of 0..n costs O(n).
Example: dp[0..8] is [0, 1, 1, 2, 1, 2, 2, 3, 1]. For i = 6 (110), 6 & 5 = 4, dp[4] = 1, so dp[6] = 2.
Negative values need care. A negative Python integer has no fixed width, so while n > 0 ends at once and returns 0. When a problem gives a 32-bit value as a signed integer, use n & 0xFFFFFFFF first. For -1 the result is 32 set bits.
60-Second Pitch
"The simple way to count set bits tests all 32 positions. I use n & (n - 1) instead. Subtracting 1 turns the lowest 1 into 0 and the zeros below it into 1s, so the AND clears exactly the lowest set bit. The loop runs once per set bit, so the time is O(K) with K at most 32, and the space is O(1). The same fact tests a power of two in one line, n > 0 and (n & (n - 1)) == 0. I keep the n > 0 guard, because zero would otherwise pass. For a signed 32-bit input, I mask with 0xFFFFFFFF first."
Common Questions
- Why does
n & (n - 1)remove exactly one set bit? Subtracting 1 flips the lowest set bit to 0 and every lower zero to 1. The bits above stay the same. The AND keeps the higher bits and clears the lowest set bit and the bits below. For
12 & 11,1100 & 1011gives1000.- What is the time complexity of
count_set_bits, and how does it compare with a loop over 32 bits? It is O(K), where K is the number of set bits, at most 32. The loop over all positions always takes 32 rounds. For a sparse value such as
2**30, Kernighan's version takes 1 round.- How do you test for a power of two, and why is
n > 0needed? Use
n > 0 and (n & (n - 1)) == 0. A power of two has one set bit, so one clear step gives 0. The number 0 also gives 0 after the step, so withoutn > 0it would be accepted. Negative numbers are rejected by the same guard.- How do you handle a negative input in Python?
A negative Python integer has no fixed width, so
while n > 0returns 0 at once. If the problem means a 32-bit value, applyn & 0xFFFFFFFFfirst. For-1, the count is then 32.- How does the trick give all bit counts from 0 to n in
O(n)? i & (i - 1)isiwith its lowest set bit removed, a smaller number. Sodp[i] = dp[i & (i - 1)] + 1. Each value takesO(1)time, as in Counting Bits (LC 338).
SWE Reasoning
Spot it
- The problem asks for the number of 1 bits (Number of 1 Bits (LC 191), Hamming weight).
- The problem asks whether a number is a power of two, or a power of four (Power of Two (LC 231), Power of Four (LC 342)).
- The loop must visit only the set bits of a mask, not all 32 positions.
- The answer for a number can be built from the answer for the same number with one set bit removed (Counting Bits (LC 338)).
The invariant, step by step
countis 0 andnholds the input.- While
n > 0,nhas at least one set bit. n &= (n - 1)clears the lowest set bit and changes nothing else.count += 1records that one set bit was removed.- So at every step,
countplus the set bits still innequals the set bits of the originaln. - When
nreaches 0, no set bit is left, andcountequals the set bits of the originaln.
Traps
- Power of two without
n > 0.is_power_of_two(0)returnsTrue, because0 & -1is 0. Add the guard. - Shifting instead of clearing.
n >>= 1removes the lowest bit whether it is 0 or 1. Ifcountstill grows each round, it counts the length ofnin bits.count_set_bits(11)returns 4 instead of 3. - Negative input.
while n > 0stops at once for a negative Python integer and returns 0. Usen & 0xFFFFFFFFfor a 32-bit signed value. - Power of four with only the one-bit test.
8has one set bit but is not a power of four. Also check the position with0x55555555.