Popcount and n & (n - 1) in Python

Why this matters

A set bit is a bit that holds 1. A number such as 12 is 1100 in binary, so it has two set bits. The count of set bits is called the popcount, short for population count. Programmers need it when they pack flags into a number, when they compress data, and when they write network code that checks masks. Interviewers ask for it because a short, correct answer shows that you know how the bits move.

This lesson builds on the bitwise operators from the earlier lesson on bit masks. It covers two ideas. The first is a loop that counts set bits. The second is one expression, n & (n - 1), that removes the lowest set bit from a number. The expression is short, but it is easy to misuse, so the lesson shows what it does one step at a time.

Set bits in a worked example

Start with a small number and write its bits out. The number 12 is 1100. Reading from the right, the columns are worth 1, 2, 4 and 8. Column 2 is set and column 3 is set, so 12 = 8 + 4. Both set columns hold a 1.

Here is a program that prints a number as eight bits, then counts its set bits by looking at every column in turn. The method n.bit_length() returns how many columns the number needs, so range(n.bit_length()) gives the numbers from 0 up to the column of the highest set bit.

The output is:

00001100 has 2 set bits

The loop runs once for each column that the number uses. In each pass, n >> i moves the bit at position i down to position 0. Then & 1 keeps only that bit. Adding the result to count gives the total.

This method takes one step per column, whatever the number is. The next method is faster for numbers with few set bits.

The trick: n & (n - 1) removes the lowest set bit

Subtracting 1 from a number has a predictable effect on its bits. Look at the lowest set bit, the rightmost 1. Subtracting 1 turns that 1 into a 0, and turns every 0 to its right into a 1. Every bit to the left of that position stays the same.

Here is 12 and the number one less than it:

The lowest set bit of 12 is in column 2, which is worth 4. Subtracting 1 turned that 1 into a 0, and turned the 0 in column 1 and the 0 in column 0 into 1s. The bit in column 3 did not change.

Now apply & (bitwise AND) to the two rows. AND keeps a column only when both rows hold a 1 there.

The only column that is 1 in both rows is the 8 column. So 12 & 11 is 8. The lowest set bit of 12 was the 4, and it has been removed.

The output is:

0b1000 8
0b100000 32
0b100 4 0b0 0

The number 40 is 101000, and its lowest set bit is the 8. The number 39 is 100111. Their AND is 100000, which is 32. The lowest set bit, 8, is gone, and everything above it is kept.

The number 6 is 110. Its lowest set bit is the 2. Applying the trick once gives 6 & 5, which is 110 & 101, which is 100, or 4. Applying it again gives 4 & 3, which is 100 & 011, which is 000, or 0.

Each application removes exactly one set bit. That is the whole idea. Repeating the operation until the number becomes 0 counts the set bits.

A longer example: 180

The number 180 is a bigger test. In binary it is 10110100, which has four set bits, worth 128, 32, 16 and 4. The loop below applies the trick one step at a time and prints each result next to its binary form:

The output is:

0b10110100
10110100 180 -> 10110000 176
10110000 176 -> 10100000 160
10100000 160 -> 10000000 128
10000000 128 -> 00000000 0

Each arrow removes the lowest set bit of the number on its left. The first step removes the 4, the second removes the 16, the third removes the 32, and the last removes the 128. There are four arrows, so there are four set bits. Nothing above the removed bit was touched at any step, which is why the next step always starts from the bit that is now lowest.

Counting set bits with the trick

Replace the column-by-column loop with a loop that runs once per set bit.

The output is:

00000000 n=0 clearing=0
00000001 n=1 clearing=1
00000110 n=6 clearing=2
00001000 n=8 clearing=1
00001100 n=12 clearing=2
11111111 n=255 clearing=8
00010000 n=16 clearing=1

Look at the row for 255. Its eight set bits take eight passes through the loop. The loop does not look at the zeros at all. A number with one set bit, such as 16, takes one pass. A number with no set bits, such as 0, takes no passes, because the loop condition n != 0 is False from the start.

The loop is a good way to understand the trick. In real Python code, you can call the method int.bit_count, which returns the same answer:

The output is:

8
8
1

The number 0xF0F0 is a hexadecimal literal, where each hex digit is four bits. It has eight set bits, four in each of its two non-zero digits. The value 1 << 40 has a single set bit in column 40, so its count is 1. The method bit_count exists on every int in Python 3.10 and later. Older versions can use bin(n).count("1"), which counts the 1 characters in the binary text.

Adding up the counts for many numbers

The popcount is often needed for a whole list of numbers. The expression below adds the set bits of every value in a list. The sum function adds the numbers that a generator gives it, and the generator calls bit_count once for each value. The total for [7, 8, 255, 1024] is 3 + 1 + 8 + 1, which is 13.

The output is:

sum 13
total for 0 to 15 32

The second total is a useful check. Each of the four columns 1, 2, 4 and 8 is 1 in exactly half of the 16 numbers from 0 to 15, so each column contributes 8 set bits, and 4 columns give 32. This is a small check that the code and the method agree with a count you can work out on paper.

What happens with negative numbers

Python shows a negative number with a minus sign, and its bit operations use an endless row of leading 1 bits. The method bit_count does not count those leading 1s. It counts the bits of the absolute value, so -6 has two set bits, the same as 6:

The output is:

2 -0b110

The trick also works on a negative number when you run a fixed number of steps, but the loop from this lesson does not end for a negative number. The next program prints five steps only, because the real loop would never stop:

The output is:

clear step -6 -8
clear step -8 -16
clear step -16 -32
clear step -32 -64
clear step -64 -128

Each step makes the number more negative, so it never reaches 0. The fix is to count the bits of abs(n), which is a positive number, or to mask the value to a fixed width first. A masked value counts only its fixed-width columns, so -6 in 8 bits (11111010) has six 1s, not two. The section on mistakes shows the same problem with the shifting loop.

Testing for a power of two

A power of two is a number such as 1, 2, 4, 8, 16 or 1024. In binary, a power of two has exactly one set bit: 1, 10, 100, 1000, and so on. A number that is not a power of two has at least two set bits, such as 6 (110) or 12 (1100).

So a test for a power of two is a test for exactly one set bit. The trick gives a direct check. For a number with exactly one set bit, the lowest set bit is the only set bit, so removing it leaves 0. That means n & (n - 1) is 0.

The output is:

0 isPowerOfTwo=False
1 isPowerOfTwo=True
2 isPowerOfTwo=True
3 isPowerOfTwo=False
4 isPowerOfTwo=True
6 isPowerOfTwo=False
8 isPowerOfTwo=True
1024 isPowerOfTwo=True
-8 isPowerOfTwo=False
-2147483648 isPowerOfTwo=False

The check n > 0 is needed for zero, and the next section shows why. Python does not wrap the smallest value of a 32-bit type, so the bare expression happens to return the right answer for -2**31. The check still states the rule directly.

In plain words, a power of two is a row with one lit switch. Subtracting 1 and then ANDing clears that one switch and leaves nothing behind. If a second switch is lit, some switch is still lit after the AND, so the result is not 0. The test checks that nothing is left over.

Choosing a counting method

There are three ways to get the popcount, and they cost different amounts of work. The table compares them for a non-negative integer.

The shift method is the easiest to read, and it is a good first version. The clearing method is faster when a number has few set bits, such as a mask with one or two flags on. The method call is the right choice in real code, because it does the work for you and you do not have to test it.

The clearing method works because of one fact. Each time n & (n - 1) runs, the number gets smaller, and it keeps the same bits above the one it removed. A count of steps is therefore a count of 1s, and no step can remove a bit that was not there. That fact holds only for non-negative numbers, because a negative number has no lowest set bit that makes it smaller.

A third example: a set of flags

Programs often store several yes-or-no settings in one number. Each setting is one column, and a 1 means the setting is on. Suppose a program has eight settings packed into one byte, and the value of the byte is 10110010. The popcount tells you how many settings are on.

The output is:

flags 10110010 on=4

Four columns hold a 1: the 128, the 32, the 16 and the 2. The popcount answers the question "how many settings are on?" in one call, without asking about each setting by name. To find out which settings are on, use a mask with & for each column, as the bit masks lesson shows.

Common mistakes

Forgetting the n > 0 check

Try the expression without the check:

The output is:

0

Zero has no set bits, so 0 & (0 - 1) gives 0, and a test that only checks for 0 would say that 0 is a power of two. Zero is not a power of two, so the check n > 0 is required.

Writing the test with the wrong operator order

In Python, & ranks above ==, so n & (n - 1) == 0 is read as (n & (n - 1)) == 0. The line works, but a reader who knows Java may expect an error there, because Java reads it differently. Write the brackets to make the meaning clear in both languages:

The output is:

False False

Both forms give False for 12, which is correct, because 12 is not a power of two.

Using >> to count a negative number

A common mistake is to count set bits by shifting right with >>, as in this loop. For a positive number, the loop works. For a negative number, >> copies the leading 1 into every column it opens up. The value settles at -1, which is all ones, and -1 >> 1 is still -1. The condition n != 0 never becomes False.

The program below prints five steps only, so it can finish:

The output is:

shift step -6
shift step -3
shift step -2
shift step -1
shift step -1

The value stops at -1. The real loop while n != 0: count += n & 1; n >>= 1 would run forever. Use abs(n) for the count, or mask the value to a fixed width first, with n & 0xFFFFFFFF for 32 bits. The shifting loop with range(n.bit_length()) from the start of this lesson avoids the problem, because it stops after the highest column.

Practice

1. Count the set bits in the binary literal 0b1011_0110 by hand. Then check your answer with int.bit_count. Underscores in a literal are ignored by Python, so the value is the same as 0b10110110.

Show the answer

By hand, the bits are 1, 0, 1, 1, 0, 1, 1, 0. There are five 1s. (0b1011_0110).bit_count() prints 5.

2. Write a function lowest_bit(n) that returns only the lowest set bit of a positive number. For example, lowest_bit(12) should return 4, because the lowest set bit of 1100 is the 4 column. Use n & (n - 1) in the function.

Show the answer

The trick gives the number with the lowest set bit removed, which is n & (n - 1). Subtracting that from n leaves only the removed bit. The function is return n - (n & (n - 1)). For 12, 12 - (12 & 11) is 12 - 8, which is 4.

3. Decide, without running code, whether 96 is a power of two. Then check your answer with the program above.

Show the answer

No. The binary form of 96 is 1100000, which has two set bits, so it is not a power of two. The expression 96 & 95 is 1100000 & 1011111, which is 1000000, or 64. That is not 0, so the test returns False.

4. How many whole numbers from 1 to 20 are powers of two? Write a loop that counts them, using is_power_of_two from this lesson.

Show the answer

Five: 1, 2, 4, 8 and 16. A loop with for i in range(1, 21): if is_power_of_two(i): count += 1 gives 5.

5. Use & to compute 1000 & 999. Explain in one sentence what the result shows about the lowest set bit of 1000.

Show the answer

The result is 992. In binary, 1000 is 1111101000 and 999 is 1111100111. Their AND is 1111100000, which is 992. The lowest set bit of 1000 is the 8 column, and the AND removed it. The bits above it are unchanged.

Summary

• The popcount of a number is the count of its set bits, and a set bit is a column that holds 1.
• The expression n & (n - 1) removes the lowest set bit of n, and it leaves every higher bit unchanged.
• Repeating n = n & (n - 1) until n is 0 gives the popcount for non-negative numbers, and it takes one step for each set bit.
• A power of two has exactly one set bit, so n > 0 and (n & (n - 1)) == 0 is a test for one.
• Zero fails the bare test, so the n > 0 check is required.
• Python's int.bit_count returns the popcount of the absolute value, and the clearing loop never ends for a negative number, so take abs(n) first.