Popcount and n & (n - 1)

Why this matters

A bit is one digit in base 2, so it holds either 0 or 1. A set bit is a bit that holds 1. The number of set bits in a number is called its popcount, which is short for population count.

Popcount answers questions such as "how many of these eight switches are on?" when the eight switches are stored as the eight bits of one byte. Programs use it in many places, from compression to game boards.

Two more uses come up often. A number is a power of two when exactly one of its bits is set, for example 1, 2, 4, 8 or 16. Table sizes and buffer sizes are often powers of two, so programs check this. Some algorithms also walk through every chosen item in a set, one at a time, and the trick in this lesson does that walk.

The bit masks lesson showed how & and | test and change single bits. This lesson uses & again, with a subtraction, to count bits. It does not repeat the operator rules.

Bits in one minute

In base 2, each position is worth twice the position to its right. Counting from the right, the positions are worth 1, 2, 4, 8, 16, 32 and so on. The number 12 is 8 plus 4, so it is written 1100 in binary. Bit 3 and bit 2 are set. Bit 1 and bit 0 are clear.

Most programs in this lesson use std::uint32_t. That is a 32-bit unsigned integer from <cstdint>. Unsigned means the type holds only zero and positive numbers. The bit patterns are easier to read this way, and the mistakes section shows what goes wrong with signed numbers.

C++20 adds std::popcount in the <bit> header. It returns the popcount of an unsigned value. The first example counts by hand so you can see what the library call does for you.

Count the bits one at a time

The simplest method looks at the lowest bit, adds one to the count if that bit is set, and then moves every bit one place to the right. Each time, the next bit becomes the lowest one.

The expression n & 1 is 1 when the lowest bit of n is set, and 0 when it is clear. This works because the number 1 has only its lowest bit set, so the & keeps only the lowest bit of n.

The statement n >>= 1 moves every bit of n one place to the right. The lowest bit falls off the end, and the top bit becomes 0. The shifts lesson later in this module covers this operator in detail. For now, read it as "remove the lowest bit and move the rest down."

Here is the method in a function:

#include <cstdint>
 
int count_by_shifting(std::uint32_t n) {
    int count = 0;
    while (n != 0) {
        count += n & 1u;
        n >>= 1;
    }
    return count;
}

Trace it on 12, which is 1100:

n = 1100   lowest bit 0   count 0   shift right -> 110
n = 110    lowest bit 0   count 0   shift right -> 11
n = 11     lowest bit 1   count 1   shift right -> 1
n = 1      lowest bit 1   count 2   shift right -> 0
n = 0      loop stops

The loop ran four times and counted two set bits. Each loop looks at one bit position, so for a 32-bit number the loop runs up to 32 times, no matter how many bits are set. That is correct, but it does more work than the method in the next section needs.

Drop the lowest set bit

The key idea is this. Take the number 12, which is 1100. Subtract 1 and you get 11, which is 1011. Compare the two numbers bit by bit:

n        = 1100   (12)
n - 1    = 1011   (11)
n & (n-1) = 1000  (8)

The lowest set bit of 12 is bit 2, which is worth 4. Subtracting 1 changes three bits. Bit 2 turns from 1 to 0. The clear bits below it, bit 1 and bit 0, turn from 0 to 1. The bits above bit 2 do not change.

The & operator keeps a bit only when both numbers have it set. Look at what happens to each group of bits:

• The bits above the lowest set bit are the same in n and n - 1. They survive the &.
• The lowest set bit is 1 in n and 0 in n - 1. The & clears it.
• The bits below the lowest set bit are 0 in n and 1 in n - 1. The & keeps them 0.

So n & (n - 1) removes exactly one set bit: the lowest one. In C++ the - binds tighter than &, so n & n - 1 means the same thing. The parentheses are there so the reader sees the order.

Here is a program that prints each step for the number 12:

#include <cstdint>
#include <iostream>
 
int main() {
    std::uint32_t n = 12;
    while (n != 0) {
        std::uint32_t next = n & (n - 1);
        std::cout << "n=" << n << " n-1=" << (n - 1) << " n&(n-1)=" << next << "\n";
        n = next;
    }
    return 0;
}

For 12 the program prints these two steps:

n=12 n-1=11 n&(n-1)=8
n=8 n-1=7 n&(n-1)=0

First 12 becomes 8, which removes bit 2. Then 8 becomes 0, which removes bit 3. Two steps, two set bits.

Counting with the drop trick

Each step removes one set bit, so the number of steps until the value is zero equals the popcount. Here is the count as a function:

#include <cstdint>
 
int count_by_dropping(std::uint32_t n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;
        ++count;
    }
    return count;
}

The loop in count_by_dropping does not look at the zero bits at all. A number with one set bit in a high position, such as 1024, runs the drop loop once. The shifting loop from the previous section looks at each position from bit 0 up to bit 10 before it reaches zero, so it runs 11 times for the same number. Both functions return 1, but the drop version does less work. The loop counts below come from a test program that counts the runs of each loop:

The dropping loop runs once per set bit, so its work depends only on the popcount. The shifting loop runs once per bit position up to the highest set bit, so a high set bit makes it slow even when only one bit is set. When every bit is set, both loops do the same amount of work.

Test for a power of two

A power of two has exactly one set bit. Examples are 1, 2, 4, 8, 16, and so on, which in binary are 1, 10, 100, 1000, 10000.

If a number has exactly one set bit, dropping that bit leaves zero. So n & (n - 1) is 0 exactly when n has one set bit or no set bits at all. The test is:

bool is_power_of_two(std::uint32_t n) {
    return n != 0 && (n & (n - 1)) == 0;
}

The first part, n != 0, is required. For n equal to 0, the subtraction 0 - 1 on an unsigned type wraps around to the largest value of the type. Then 0 & (largest value) is 0, so the second part alone says that zero is a power of two. Zero is not a power of two, so the first part is needed.

The C++20 library has this test built in. std::has_single_bit is in <bit>, returns true for powers of two, and returns false for zero. Use it in real code. Writing the test by hand shows you why it works.

The full program for this section is in the next block. It shows the power-of-two test for a few values, and the count functions for the same numbers:

#include <bit>
#include <cstdint>
#include <iostream>
 
// Count set bits by testing the lowest bit and shifting right.
int count_by_shifting(std::uint32_t n) {
    int count = 0;
    while (n != 0) {
        count += n & 1u;
        n >>= 1;
    }
    return count;
}
 
// Count set bits by dropping the lowest set bit each time.
int count_by_dropping(std::uint32_t n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;
        ++count;
    }
    return count;
}
 
int main() {
    std::uint32_t values[] = {0, 1, 12, 255, 1024, 0xFFFFFFFFu};
    for (std::uint32_t v : values) {
        std::cout << v << " shift=" << count_by_shifting(v)
                  << " drop=" << count_by_dropping(v)
                  << " std=" << std::popcount(v) << "\n";
    }
 
    // Trace of n &= n - 1 for 12.
    std::uint32_t n = 12;
    while (n != 0) {
        std::uint32_t next = n & (n - 1);
        std::cout << "n=" << n << " n-1=" << (n - 1) << " n&(n-1)=" << next << "\n";
        n = next;
    }
 
    // Power-of-two test.
    for (std::uint32_t v : {0u, 1u, 2u, 3u, 8u, 12u, 64u}) {
        bool p = v != 0 && (v & (v - 1)) == 0;
        std::cout << v << " power of two? " << std::boolalpha << p << "\n";
    }
    return 0;
}

Output from a run with g++ -std=c++20 -Wall:

0 shift=0 drop=0 std=0
1 shift=1 drop=1 std=1
12 shift=2 drop=2 std=2
255 shift=8 drop=8 std=8
1024 shift=1 drop=1 std=1
4294967295 shift=32 drop=32 std=32
n=12 n-1=11 n&(n-1)=8
n=8 n-1=7 n&(n-1)=0
0 power of two? false
1 power of two? true
2 power of two? true
3 power of two? false
8 power of two? true
12 power of two? false
64 power of two? true

When you meet n & (n - 1) in someone else's code, read it as "remove the lowest set bit." That reading is faster than working out the bits each time.

The three counting methods agree on every value. The power-of-two test gives true for 1, 2, 8 and 64, and false for 0, 3 and 12.

Worked example 2: which switches are on

The first example counted bits. This one also needs the position of each set bit. Take a byte of eight switches. Bit 0 is switch 0, and bit 7 is switch 7. A set bit means the switch is on.

The library function std::countr_zero counts how many zero bits sit at the low end of a number. For a non-zero number, that count is the position of the lowest set bit. Combine it with the drop trick and you can list every position in order.

#include <bit>
#include <cstdint>
#include <iostream>
 
int main() {
    // Eight switches. Bit 0 is switch 0, bit 7 is switch 7.
    std::uint8_t switches = 0b1010'0110;
    std::cout << "lit switches: " << std::popcount(switches) << "\n";
 
    // Print the position of each lit switch, lowest first.
    std::cout << "positions:";
    std::uint8_t rest = switches;
    while (rest != 0) {
        int position = std::countr_zero(rest);
        std::cout << " " << position;
        rest &= rest - 1;
    }
    std::cout << "\n";
 
    // Exactly one switch on? That is a power-of-two test on the mask.
    for (std::uint8_t mask : {std::uint8_t{0}, std::uint8_t{0b0000'0100}, std::uint8_t{0b0001'0100}}) {
        bool exactly_one = mask != 0 && (mask & (mask - 1)) == 0;
        std::cout << "mask " << static_cast<int>(mask) << " exactly one on: "
                  << std::boolalpha << exactly_one << "\n";
    }
 
    // Check the drop trick against std::popcount for every 16-bit value.
    int mismatches = 0;
    for (std::uint32_t v = 0; v <= 0xFFFF; ++v) {
        int count = 0;
        std::uint32_t n = v;
        while (n != 0) {
            n &= n - 1;
            ++count;
        }
        if (count != std::popcount(v)) {
            ++mismatches;
        }
    }
    std::cout << "mismatches over 0..65535: " << mismatches << "\n";
    return 0;
}

Output:

lit switches: 4
positions: 1 2 5 7
mask 0 exactly one on: false
mask 4 exactly one on: true
mask 20 exactly one on: false
mismatches over 0..65535: 0

The byte 0b1010'0110 is 166 in decimal. Its set bits are bits 1, 2, 5 and 7, which is 2 + 4 + 32 + 128. So switches 1, 2, 5 and 7 are on. The output shows exactly those positions.

The mask 0b0000'0100 is 4, which has one set bit, so the test says exactly one switch is on. The mask 0b0001'0100 is 20, which has two set bits, so the test says no.

The digit separator ' in 0b1010'0110 is a C++14 feature. It only changes how the literal is written, not its value.

Worked example 3: check a bit trick against the library

When you write a bit trick, check it against a trusted version on many inputs. The last loop in the program above does this. It runs the drop loop on every value from 0 to 65535, which is every 16-bit number, and compares the result with std::popcount. The count of disagreements is 0.

The check finds errors that a few hand-picked values would miss. A 16-bit range is small enough to cover completely. For a 32-bit or 64-bit type, you cannot check every value, so check random values or the edge values, such as 0, 1, the largest value and the values with one bit set.

This habit is useful for any bit trick, not only this one.

Common mistakes

Forgetting the zero check

The power-of-two test needs n != 0. Without it, zero passes the test. The program below prints what happens:

#include <iostream>
 
int main() {
    unsigned int zero = 0;
    std::cout << "zero & (zero - 1) == 0 is " << std::boolalpha
              << ((zero & (zero - 1)) == 0) << "\n";
    return 0;
}

Output:

zero & (zero - 1) == 0 is true

The fix is the first part of the test, n != 0 && .... std::has_single_bit already returns false for zero.

Calling std::popcount on a signed int

std::popcount accepts only unsigned integer types. Passing an int is a compile error. This program is a small example:

#include <bit>
#include <iostream>
 
int main() {
    unsigned int zero = 0;
    // Without the n != 0 guard, zero passes the power-of-two test.
    std::cout << "zero & (zero - 1) == 0 is " << std::boolalpha
              << ((zero & (zero - 1)) == 0) << "\n";
 
    int signed_value = 12;
    std::cout << "std::popcount(signed) = " << std::popcount(signed_value) << "\n";
    return 0;
}

The first lines of the error from g++ -std=c++20 -Wall, with the rest of the message shortened, are:

pop2.cpp:11:61: error: no matching function for call to 'popcount(int&)'
   11 |     std::cout << "std::popcount(signed) = " << std::popcount(signed_value) << "\n";
      |                                                ~~~~~~~~~~~~~^~~~~~~~~~~~~~
pop2.cpp:11:61: note: there is 1 candidate
...
note: the expression 'std::__is_unsigned_integer<_Tp>::value [with _Tp = int]' evaluated to 'false'

Because the call is rejected, the program does not build, so there is no run output.

The message names the problem: the candidate needs an unsigned integer type, and int is not one. Declare the variable as unsigned int, or convert it with static_cast<unsigned int>(signed_value) when you know the value is not negative. Other compilers word this error differently, but they reject the same call.

Using the drop trick on a negative number

The drop trick is meant for unsigned values. On a negative int, the sign bit is set, and the bit pattern does not behave like a count of ones. The program below uses the signed value -8:

#include <bit>
#include <cstdint>
#include <iostream>
#include <limits>
 
int main() {
    // Signed drop trick on a negative number: -8 & -9.
    int a = -8;
    std::cout << "-8 & (-8 - 1) = " << (a & (a - 1)) << "\n";
 
    // Unsigned version of the same bit pattern.
    unsigned int b = static_cast<unsigned int>(-8);
    std::cout << "unsigned -8 has " << std::popcount(b) << " set bits\n";
    return 0;
}

Output:

-8 & (-8 - 1) = -16
unsigned -8 has 29 set bits

The value -8 has 29 set bits in its 32-bit form, because the sign bit and the high bits are all 1. Dropping the lowest set bit gives -16, which is still negative. A loop that runs until the value is zero never stops here, because the value keeps getting more negative. Use an unsigned type for bit counting.

Subtracting from the smallest int

In a signed type, INT_MIN - 1 is outside the range of the type. The C++ standard calls this undefined behaviour, which means the standard does not say what happens. The next program, which combines the earlier checks, runs that subtraction on its last line:

#include <bit>
#include <cstdint>
#include <iostream>
#include <limits>
 
int main() {
    unsigned int zero = 0;
    std::cout << "zero & (zero - 1) == 0 is " << std::boolalpha
              << ((zero & (zero - 1)) == 0) << "\n";
 
    // Signed drop trick on a negative number: -8 & -9.
    int a = -8;
    std::cout << "-8 & (-8 - 1) = " << (a & (a - 1)) << "\n";
 
    // Unsigned version of the same bit pattern.
    unsigned int b = static_cast<unsigned int>(-8);
    std::cout << "unsigned -8 has " << std::popcount(b) << " set bits\n";
 
    std::uint64_t big = 0xF0F0'F0F0'F0F0'F0F0u;
    std::cout << "popcount of 0xF0F0F0F0F0F0F0F0 = " << std::popcount(big) << "\n";
 
    // Signed INT_MIN minus 1 is undefined behaviour; this line runs it on purpose.
    int m = std::numeric_limits<int>::min();
    std::cout << "INT_MIN & (INT_MIN - 1) = " << (m & (m - 1)) << "\n";
    return 0;
}

A normal build prints every line and gives no warning. The last line prints 0 here, which is only what this build happened to do:

zero & (zero - 1) == 0 is true
-8 & (-8 - 1) = -16
unsigned -8 has 29 set bits
popcount of 0xF0F0F0F0F0F0F0F0 = 32
INT_MIN & (INT_MIN - 1) = 0

Build it again with the undefined behaviour checker that GCC provides, -fsanitize=undefined, and the checker prints a message before the same lines:

pop3.cpp:24:58: runtime error: signed integer overflow: -2147483648 - 1 cannot be represented in type 'int'

The checker is a debugging tool. It slows the program, so use it while you test, not in the final build. The fix for this kind of bug is the same as before: count bits in unsigned types, where subtracting 1 from 0 wraps around instead of breaking the rules.

Practice

Exercise 1

Write a function int count_bits(std::uint64_t n) that counts the set bits with the drop method. Run it on 0, 1 and ~0ull, which is the value with all 64 bits set. What does each call print?

Show the answer

The function is the same loop as count_by_dropping, with a 64-bit parameter:

int count_bits(std::uint64_t n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;
        ++count;
    }
    return count;
}

The calls print count_bits(0) = 0, count_bits(1) = 1 and count_bits(~0ull) = 64. All 64 bits are set in ~0ull, so the loop runs 64 times. A test program with this function printed those three values.

Exercise 2

How many loops does while (n != 0) n &= n - 1; take for n = 40? Work it out on paper first, then check.

Show the answer

The number 40 is 101000 in binary, which has two set bits, so the loop runs two times. The steps are 40 & 39 = 32, then 32 & 31 = 0. A run of the program gives 40 & 39 = 32 and loops for 40 = 2.

Exercise 3

Is 96 a power of two? Explain with bits, not by trying every power of two.

Show the answer

No. The number 96 is 1100000 in binary, which has two set bits, the bits worth 64 and 32. The test gives 96 & 95 = 64, which is not zero, so the test says false. A run prints 96 & 95 = 64 popcount 96 = 2.

Exercise 4

List the positions of the set bits in 0b0110'1001, lowest first. Use std::countr_zero and the drop trick.

Show the answer

The positions are 0, 3, 5 and 6. The byte is 105, which is 1 + 8 + 32 + 64. A loop that prints std::countr_zero(rest) and then runs rest &= rest - 1 prints 0 3 5 6.

Exercise 5

Why does 16 & 15 equal 0?

Show the answer

The number 16 is 10000 in binary, with only bit 4 set. The number 15 is 01111, with bits 0 to 3 set. They have no set bit in common, so the & gives 0. This is the same reason that n & (n - 1) is 0 for every power of two.

Summary

• The popcount of a number is how many of its bits are 1.
• The expression n & (n - 1) removes the lowest set bit of n.
• Repeating that step until the value is 0 counts the set bits, and it runs once per set bit.
• A power of two has one set bit, so n != 0 && (n & (n - 1)) == 0 tests for it.
• Use unsigned types with bit counting. std::popcount and std::has_single_bit in <bit> do the same work and reject signed input.