C++ bitwise operators and the <bit> header

C++ has six bitwise operators, which work on the individual bits of integers rather than on their values as numbers: & (and), | (or), ^ (exclusive or), ~ (not), << (shift left) and >> (shift right). With them one integer can hold many yes-or-no flags, a small set, or the packed fields of a file format, a network header or a hardware register. The <bit> header, new in C++20, adds named functions for jobs that used to need tricks: std::popcount counts the 1 bits, std::countr_zero finds the lowest one and std::bit_width says how many bits a number needs. Two rules prevent most bit bugs: work on unsigned types, and keep every shift count between 0 and the width of the type minus 1, because any other count is undefined behaviour. This lesson shows each operator, the masks built from them, the shifts that are undefined and the <bit> functions, every example built with Apple clang 21 and GCC 16.

The six operators on one byte

The program below applies each operator to two 8-bit values and prints them in binary. 0b starts a binary literal, the ' between digits only makes it easier to read, and {:08b} asks std::println for eight binary digits:

// The six bitwise operators on two 8-bit values, printed in binary.
#include <cstdint>
#include <print>

int main() {
    const std::uint8_t a = 0b1100'1010;  // 202
    const std::uint8_t b = 0b0101'0110;  //  86

    std::println("a       {:08b}", a);
    std::println("b       {:08b}", b);
    std::println("a & b   {:08b}  1 where both bits are 1", a & b);
    std::println("a | b   {:08b}  1 where either bit is 1", a | b);
    std::println("a ^ b   {:08b}  1 where the bits differ", a ^ b);
    std::println("a >> 3  {:08b}  moved 3 places right, zeros come in on the left", a >> 3);

    // a is promoted to int before ~ and << work on it, so both results are ints.
    std::println("~a      {} as an int, {:08b} once it is put back in a byte", ~a,
                 static_cast<std::uint8_t>(~a));
    std::println("a << 1  {} as an int ({:b}): the ninth bit is kept", a << 1, a << 1);

    // Right-shifting a negative value copies the sign bit, which rounds down (since C++20).
    std::println("-21 >> 2 = {}, but -21 / 4 = {}", -21 >> 2, -21 / 4);
}

Every C++ example in this track is compiled and run by a short session file that lists the commands, the way you would type them in a terminal (the first lesson shows how to run one yourself). The recorded output shows each command after $, then what it printed:

from session import run

run("""
clang++ --version | head -n 1
clang++ -std=c++23 -Wall -Wextra bit_ops.cpp -o bit_ops && ./bit_ops
g++-16 --version | head -n 1
g++-16 -std=c++23 -Wall -Wextra bit_ops.cpp -o bit_ops && ./bit_ops
""")

$ clang++ --version | head -n 1
Apple clang version 21.0.0 (clang-2100.3.34.2)
$ clang++ -std=c++23 -Wall -Wextra bit_ops.cpp -o bit_ops && ./bit_ops
a       11001010
b       01010110
a & b   01000010  1 where both bits are 1
a | b   11011110  1 where either bit is 1
a ^ b   10011100  1 where the bits differ
a >> 3  00011001  moved 3 places right, zeros come in on the left
~a      -203 as an int, 00110101 once it is put back in a byte
a << 1  404 as an int (110010100): the ninth bit is kept
-21 >> 2 = -6, but -21 / 4 = -5
$ g++-16 --version | head -n 1
g++-16 (Homebrew GCC 16.2.0) 16.2.0
$ g++-16 -std=c++23 -Wall -Wextra bit_ops.cpp -o bit_ops && ./bit_ops
a       11001010
b       01010110
a & b   01000010  1 where both bits are 1
a | b   11011110  1 where either bit is 1
a ^ b   10011100  1 where the bits differ
a >> 3  00011001  moved 3 places right, zeros come in on the left
~a      -203 as an int, 00110101 once it is put back in a byte
a << 1  404 as an int (110010100): the ninth bit is kept
-21 >> 2 = -6, but -21 / 4 = -5

Each operator decides every bit of the result on its own, from the bits in the same position:

• a & b, and: a bit of the result is 1 when both bits are 1. Use it to keep or test chosen bits (masking).
• a | b, or: 1 when either bit is 1. Use it to set chosen bits.
• a ^ b, exclusive or: 1 when the two bits differ. Use it to flip chosen bits, or to find what changed.
• ~a, not: 1 when the bit of a is 0. Use it to build a mask of “every other bit”.
• a << n, shift left: 1 when the bit n places lower was 1. Use it to multiply by 2ⁿ or to build a one-bit mask.
• a >> n, shift right: 1 when the bit n places higher was 1. Use it to divide by 2ⁿ or to take out a field.

The last three lines of the output hold the two surprises of this lesson. First, ~a printed -203 and a << 1 printed 404. Before an operator works on a type narrower than int, such as std::uint8_t, char or bool, the value is converted to int (the standard calls this an integral promotion), so the result is an int of 32 bits: ~a flips all 32, giving a negative number, and a << 1 keeps the ninth bit instead of dropping it. Put the result back into a byte with static_cast<std::uint8_t> when a byte is what you want. A test such as ~a == 0b0011'0101 is false for the same reason.

Second, >> on a negative number copies the sign bit into the bits it frees, which rounds towards minus infinity: -21 >> 2 is -6, while -21 / 4, which rounds towards zero, is -5. C++20 made that behaviour part of the standard; before it, right-shifting a negative value gave a result each compiler chose. Neither surprise exists for unsigned types of at least int’s width, which is why bit code is written with unsigned, std::uint32_t and std::uint64_t.

One more trap is precedence: == binds more tightly than &, so x & 1 == 0 means x & (1 == 0), which is always 0. Write (x & 1) == 0. Both compilers warn about the first form under -Wall (the warning is -Wparentheses).

Masks: setting, clearing and testing one bit

A mask is a value with 1s exactly where you want to act. The mask for bit i is 1u << i, and four idioms cover almost every use of a flag word:

• set bit i: flags |= 1u << i;
• clear bit i: flags &= ~(1u << i);
• flip bit i: flags ^= 1u << i;
• test bit i: (flags >> i) & 1u, which is 1 or 0.

The same idea turns an integer into a set. With n items, bit i of a mask says whether item i is in the set, so the 2ⁿ numbers from 0 to 2ⁿ - 1 are exactly the 2ⁿ subsets. The program below lists every subset of {a, b, c} and visits the members of each subset with two operations that are worth remembering: std::countr_zero(rest) gives the position of the lowest 1 bit, and rest &= rest - 1 clears it.

// Every subset of {a, b, c}: bit i of the mask says whether item i is in the subset.
#include <array>
#include <bit>
#include <print>
#include <string>

int main() {
    constexpr std::array items{'a', 'b', 'c'};
    constexpr unsigned n = items.size();

    for (unsigned mask = 0; mask < (1u << n); ++mask) {
        std::string subset;
        // Visit the set bits from the lowest: countr_zero finds it, rest &= rest - 1 clears it.
        for (unsigned rest = mask; rest != 0; rest &= rest - 1) {
            if (!subset.empty()) subset += ", ";
            subset += items[std::countr_zero(rest)];
        }
        std::println("{:03b}  {{{}}}  size {}", mask, subset, std::popcount(mask));
    }
}

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined subsets.cpp -o subsets && ./subsets
g++-16 -std=c++23 -Wall -Wextra -fsanitize=address,undefined subsets.cpp -o subsets && ./subsets
""")

$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined subsets.cpp -o subsets && ./subsets
000  {}  size 0
001  {a}  size 1
010  {b}  size 1
011  {a, b}  size 2
100  {c}  size 1
101  {a, c}  size 2
110  {b, c}  size 2
111  {a, b, c}  size 3
$ g++-16 -std=c++23 -Wall -Wextra -fsanitize=address,undefined subsets.cpp -o subsets && ./subsets
000  {}  size 0
001  {a}  size 1
010  {b}  size 1
011  {a, b}  size 2
100  {c}  size 1
101  {a, c}  size 2
110  {b, c}  size 2
111  {a, b, c}  size 3

Read the masks from the right: the last digit is item a, so 011 is {a, b} and 100 is {c}. The size of each subset is simply std::popcount(mask), the number of 1 bits. Each extra item doubles the number of subsets, so listing them all is practical up to about 20 items (1,048,576 subsets) and hopeless at 40.

Why does rest &= rest - 1 clear the lowest 1 bit? Subtracting 1 turns that bit into 0 and every 0 below it into 1, while the bits above it stay as they are, so the and of the two keeps only the bits above. A close relative, x & -x, keeps only the lowest 1 bit, because -x on an unsigned value is ~x + 1:

Shifts that are undefined behaviour

The rules for << and >> are in section 7.6.7 of the C++23 standard. The shift count must be at least 0 and less than the width of the promoted left operand: 32 for int and unsigned, 64 for std::uint64_t. A count outside that range is undefined behaviour, so the program has no meaning at all, whatever the processor happens to do. Inside the range, everything is defined since C++20: a left shift keeps the low N bits of the true result (a 1 may land in the sign bit), and a right shift rounds down. Before C++20, shifting a negative value left was undefined too, and so was a left shift whose result did not fit in the unsigned version of the type, such as 3 << 31.

The program below reads the value and the count from the command line, so neither compiler can see them in advance. -fsanitize=undefined adds the checks of UndefinedBehaviorSanitizer (UBSan), which report the problem while the program runs:

// Shifts a value by a count. Both come from the command line,
// so the compiler cannot check them in advance.
#include <iostream>
#include <string>

int main(int argc, char* argv[]) {
    if (argc != 3) return 2;
    const int value = std::stoi(argv[1]);
    const int count = std::stoi(argv[2]);
    std::cout << value << " << " << count << " = " << (value << count) << '\n';
}

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra -fsanitize=undefined shift.cpp -o shift
./shift 1 31
./shift -20 2
./shift 1 32
./shift 1 -1
g++-16 -std=c++23 -Wall -Wextra -fsanitize=undefined shift.cpp -o shift
./shift 1 31
./shift 1 32
# The same program built as C++17, under the older rules for shifts:
clang++ -std=c++17 -Wall -Wextra -fsanitize=undefined shift.cpp -o shift17
./shift17 -20 2
./shift17 3 31
""")

$ clang++ -std=c++23 -Wall -Wextra -fsanitize=undefined shift.cpp -o shift
$ ./shift 1 31
1 << 31 = -2147483648
$ ./shift -20 2
-20 << 2 = -80
$ ./shift 1 32
shift.cpp:10:62: runtime error: shift exponent 32 is too large for 32-bit type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior shift.cpp:10:62
1 << 32 = 1
$ ./shift 1 -1
shift.cpp:10:62: runtime error: shift exponent -1 is negative
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior shift.cpp:10:62
1 << -1 = -2147483648
$ g++-16 -std=c++23 -Wall -Wextra -fsanitize=undefined shift.cpp -o shift
$ ./shift 1 31
1 << 31 = -2147483648
$ ./shift 1 32
shift.cpp:10:62: runtime error: shift exponent 32 is too large for 32-bit type 'int'
1 << 32 = 1
# The same program built as C++17, under the older rules for shifts:
$ clang++ -std=c++17 -Wall -Wextra -fsanitize=undefined shift.cpp -o shift17
$ ./shift17 -20 2
shift.cpp:10:62: runtime error: left shift of negative value -20
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior shift.cpp:10:62
-20 << 2 = -80
$ ./shift17 3 31
shift.cpp:10:62: runtime error: left shift of 3 by 31 places cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior shift.cpp:10:62
3 << 31 = -2147483648

What the session shows:

• 1 << 31 is -2147483648 without a report: since C++20 that is the defined result, the bit pattern of 0x80000000 read as an int. It is rarely the value a mask needs; 1u << 31 is 2147483648.
• -20 << 2 is -80 without a report in C++23, while the same program built as C++17 gets a report, because the old rules made shifting a negative value left undefined; so does 3 << 31, whose result needs 33 bits.
• Counts 32 and -1 are reported by both compilers. The numbers printed after the reports are whatever the arm64 shift instruction produced on this Mac (1 for a count of 32, as if it were 0); another processor, or another level of optimisation, may print something else, and that is what undefined means.

When the count is a constant, the compiler checks it itself. In a constant expression it must, because a constant expression is never allowed to contain undefined behaviour, so both compilers reject this line:

// The same mistake in a constant expression: the compiler must reject it.
constexpr int mask = 1 << 32;

int main() { return mask; }

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra constant_shift.cpp -o constant_shift
g++-16 -std=c++23 -Wall -Wextra constant_shift.cpp -o constant_shift
""")

$ clang++ -std=c++23 -Wall -Wextra constant_shift.cpp -o constant_shift
constant_shift.cpp:2:15: error: constexpr variable 'mask' must be initialized by a constant expression
    2 | constexpr int mask = 1 << 32;
      |               ^      ~~~~~~~
constant_shift.cpp:2:24: note: shift count 32 >= width of type 'int' (32 bits)
    2 | constexpr int mask = 1 << 32;
      |                        ^
1 error generated.
[exit status 1]
$ g++-16 -std=c++23 -Wall -Wextra constant_shift.cpp -o constant_shift
constant_shift.cpp:2:24: warning: left shift count >= width of type [-Wshift-count-overflow]
    2 | constexpr int mask = 1 << 32;
      |                      ~~^~~~~
constant_shift.cpp:2:24: error: right operand of shift expression '(1 << 32)' is greater than or equal to the precision 32 of the left operand [-fpermissive]
[exit status 1]

So build a one-bit mask from a value as wide as the bit number needs: std::uint64_t{1} << i or 1ULL << i for bits up to 63, and check 0 <= i && i < 64 first whenever i comes from input. The constexpr lesson shows more mistakes that constant expressions catch.

The <bit> header

C++20 added <bit> with functions for the questions that bit code keeps asking, and C++23 added std::byteswap. For one 8-bit value:

// What the functions of <bit> (C++20) return for one 8-bit value and one 32-bit value.
#include <bit>
#include <cstdint>
#include <print>

int main() {
    const std::uint8_t x = 0b0010'1100;  // 44
    std::println("x                 {:08b} ({})", x, x);
    std::println("popcount(x)       {}  bits that are 1", std::popcount(x));
    std::println("countr_zero(x)    {}  zeros below the lowest 1", std::countr_zero(x));
    std::println("countl_zero(x)    {}  zeros above the highest 1, in 8 bits", std::countl_zero(x));
    std::println("bit_width(x)      {}  bits needed to write x", std::bit_width(x));
    std::println("has_single_bit(x) {}", std::has_single_bit(x));
    std::println("bit_floor(x)      {}  largest power of two <= x", std::bit_floor(x));
    std::println("bit_ceil(x)       {}  smallest power of two >= x", std::bit_ceil(x));
    std::println("rotl(x, 3)        {:08b}  bits leaving on the left return on the right", std::rotl(x, 3));

    const std::uint32_t y = 0x12345678;
    std::println("byteswap(y)       {:#010x}  (C++23)", std::byteswap(y));
    std::println("countl_zero(1u)   {}  the same value, 32 bits wide", std::countl_zero(1u));
}

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra bit_header.cpp -o bit_header && ./bit_header
g++-16 -std=c++23 -Wall -Wextra bit_header.cpp -o bit_header && ./bit_header
""")

$ clang++ -std=c++23 -Wall -Wextra bit_header.cpp -o bit_header && ./bit_header
x                 00101100 (44)
popcount(x)       3  bits that are 1
countr_zero(x)    2  zeros below the lowest 1
countl_zero(x)    2  zeros above the highest 1, in 8 bits
bit_width(x)      6  bits needed to write x
has_single_bit(x) false
bit_floor(x)      32  largest power of two <= x
bit_ceil(x)       64  smallest power of two >= x
rotl(x, 3)        01100001  bits leaving on the left return on the right
byteswap(y)       0x78563412  (C++23)
countl_zero(1u)   31  the same value, 32 bits wide
$ g++-16 -std=c++23 -Wall -Wextra bit_header.cpp -o bit_header && ./bit_header
x                 00101100 (44)
popcount(x)       3  bits that are 1
countr_zero(x)    2  zeros below the lowest 1
countl_zero(x)    2  zeros above the highest 1, in 8 bits
bit_width(x)      6  bits needed to write x
has_single_bit(x) false
bit_floor(x)      32  largest power of two <= x
bit_ceil(x)       64  smallest power of two >= x
rotl(x, 3)        01100001  bits leaving on the left return on the right
byteswap(y)       0x78563412  (C++23)
countl_zero(1u)   31  the same value, 32 bits wide

• std::popcount(x) counts the 1 bits: 3.
• std::countr_zero(x) counts the 0 bits below the lowest 1 (2), and std::countl_zero(x) the 0 bits above the highest 1. The second depends on the width of the type: 2 for the 8-bit x, but 31 for 1u, a 32-bit value. std::countr_one and std::countl_one count 1 bits the same way.
• std::bit_width(x) is the number of bits needed to write x, 6 for 44, which is also the floor of log₂(x) plus 1.
• std::has_single_bit(x) is true for powers of two. std::bit_floor(x) and std::bit_ceil(x) round down and up to a power of two; bit_ceil requires the result to fit in the type, so std::bit_ceil(std::uint8_t{200}), which would be 256, is undefined.
• std::rotl(x, 3) shifts left, and the bits that fall off the top come back at the bottom; std::rotr goes the other way.
• std::byteswap(y) reverses the order of the bytes of an integer, the step between little-endian and big-endian data.

Every one of these functions takes only unsigned integer types. 5 is an int, so std::popcount(5) does not compile, and neither does std::popcount('a'):

// The functions of <bit> accept only unsigned integer types: 5 is an int.
#include <bit>

int main() { return std::popcount(5); }

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra signed_popcount.cpp -o signed_popcount
g++-16 -std=c++23 -Wall -Wextra signed_popcount.cpp -o signed_popcount
""", max_lines=8)

$ clang++ -std=c++23 -Wall -Wextra signed_popcount.cpp -o signed_popcount
signed_popcount.cpp:4:21: error: no matching function for call to 'popcount'
    4 | int main() { return std::popcount(5); }
      |                     ^~~~~~~~~~~~~
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__bit/popcount.h:32:51: note: candidate template ignored: constraints not satisfied [with _Tp = int]
   32 | [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr int popcount(_Tp __t) noexcept {
      |                                                   ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__bit/popcount.h:31:11: note: because 'int' does not satisfy '__unsigned_integer'
   31 | template <__unsigned_integer _Tp>
[5 more lines]
[exit status 1]
$ g++-16 -std=c++23 -Wall -Wextra signed_popcount.cpp -o signed_popcount
signed_popcount.cpp: In function 'int main()':
signed_popcount.cpp:4:34: error: no matching function for call to 'popcount(int)'
    4 | int main() { return std::popcount(5); }
      |                     ~~~~~~~~~~~~~^~~
  • there is 1 candidate
In file included from signed_popcount.cpp:2:
    • candidate 1: 'template<class _Tp>  requires  __unsigned_integer<_Tp> constexpr int std::popcount(_Tp)'
      /opt/homebrew/Cellar/gcc/16.2.0/include/c++/16/bit:446:5:
[17 more lines]
[exit status 1]

Write std::popcount(5u), or convert a signed value on purpose with static_cast<unsigned>(x). The refusal is deliberate: the standard states the constraint “T is an unsigned integer type” for every function in this group. For a negative number the answer would depend on the width of the type: -1 has 32 bits set as an int and 64 as a long long.

Is std::popcount faster than a loop?

Here are three ways to count the 1 bits of a 64-bit value, and a program that checks that they agree on three million pseudo-random values:

// Three ways to count the 1 bits of a 64-bit value.
// extern "C" keeps the function names readable in the assembly.
#include <bit>
#include <cstdint>

extern "C" int with_library(std::uint64_t x) { return std::popcount(x); }

extern "C" int clear_lowest(std::uint64_t x) {
    int count = 0;
    for (; x != 0; x &= x - 1) ++count;  // each step clears the lowest 1 bit
    return count;
}

extern "C" int bit_by_bit(std::uint64_t x) {
    int count = 0;
    for (int i = 0; i < 64; ++i) count += static_cast<int>((x >> i) & 1);
    return count;
}

// Checks that the three functions of popcount_ways.cpp agree,
// on a million pseudo-random values and on the extremes.
#include <cstdint>
#include <print>

extern "C" int with_library(std::uint64_t x);
extern "C" int clear_lowest(std::uint64_t x);
extern "C" int bit_by_bit(std::uint64_t x);

int main() {
    std::uint64_t x = 0x9E3779B97F4A7C15;  // a fixed seed, so every run checks the same values
    int checked = 0;
    for (int i = 0; i < 1'000'000; ++i) {
        x ^= x << 13;  // xorshift64: a simple pseudo-random sequence
        x ^= x >> 7;
        x ^= x << 17;
        for (std::uint64_t v : {x, x & 0xFFFF, x >> 40}) {
            const int expected = with_library(v);
            if (clear_lowest(v) != expected || bit_by_bit(v) != expected) {
                std::println("mismatch at {:#x}", v);
                return 1;
            }
            ++checked;
        }
    }
    std::println("{} values checked; popcount(0) = {}, popcount(~0) = {}", checked, with_library(0),
                 with_library(~std::uint64_t{0}));
}

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra -O2 popcount_check.cpp popcount_ways.cpp -o check && ./check
g++-16 -std=c++23 -Wall -Wextra -O2 popcount_check.cpp popcount_ways.cpp -o check && ./check
# The machine code of each function, with -O2: its name, then any line with cnt (the arm64 instruction that counts bits)
clang++ -std=c++23 -O2 -S -o - popcount_ways.cpp | grep -E '^_[a-z_]+:|cnt'
g++-16 -std=c++23 -O2 -S -o - popcount_ways.cpp | grep -E '^_[a-z_]+:|cnt'
""")

$ clang++ -std=c++23 -Wall -Wextra -O2 popcount_check.cpp popcount_ways.cpp -o check && ./check
3000000 values checked; popcount(0) = 0, popcount(~0) = 64
$ g++-16 -std=c++23 -Wall -Wextra -O2 popcount_check.cpp popcount_ways.cpp -o check && ./check
3000000 values checked; popcount(0) = 0, popcount(~0) = 64
# The machine code of each function, with -O2: its name, then any line with cnt (the arm64 instruction that counts bits)
$ clang++ -std=c++23 -O2 -S -o - popcount_ways.cpp | grep -E '^_[a-z_]+:|cnt'
_with_library:                          ; @with_library
	cnt.8b	v0, v0
_clear_lowest:                          ; @clear_lowest
	cnt.8b	v0, v0
_bit_by_bit:                            ; @bit_by_bit
$ g++-16 -std=c++23 -O2 -S -o - popcount_ways.cpp | grep -E '^_[a-z_]+:|cnt'
_with_library:
	cnt	v31.8b, v31.8b
_clear_lowest:
	cnt	v31.8b, v31.8b
_bit_by_bit:

All three agree. The last two commands ask each compiler for the arm64 machine code of the three functions (-S writes assembly) and keep only the function names and the lines with cnt, the arm64 instruction that counts the 1 bits of each byte. Both compilers turned std::popcount into cnt, and both recognised the clear-the-lowest-bit loop and gave it the same instruction; the bit-by-bit loop became a longer loop without it. So std::popcount says what you mean and is as fast as the hardware allows, without relying on the optimiser to recognise your loop.

Exercise: a set of the numbers 0 to 63

Write the five member functions of Bitset64, a set of the numbers 0 to 63 stored in the bits of one std::uint64_t: set(i) puts i in the set, reset(i) takes it out, test(i) says whether it is in, count() says how many numbers are in, and lowest_set() returns the smallest number in the set, or -1 when the set is empty. Each one is a single line. The checks in main must all print ok:

// Exercise: a set of the numbers 0 to 63, stored in the bits of one std::uint64_t.
// Write the five member functions, then build and run this file: every check must say "ok".
#include <bit>
#include <cstdint>
#include <print>

struct Bitset64 {
    std::uint64_t bits = 0;

    void set(int i) { (void)i; }                      // put i in the set
    void reset(int i) { (void)i; }                    // take i out of the set
    bool test(int i) const { (void)i; return false; } // is i in the set?
    int count() const { return 0; }                   // how many numbers are in the set
    int lowest_set() const { return 0; }              // the smallest number in it, or -1 if empty
};

int failures = 0;

void check(bool passed, const char* what) {
    std::println("{}  {}", passed ? "ok    " : "FAILED", what);
    if (!passed) ++failures;
}

int main() {
    Bitset64 s;
    check(s.count() == 0 && s.lowest_set() == -1, "a new set is empty");
    s.set(3);
    s.set(40);
    check(s.test(3) && s.test(40) && !s.test(4), "set(3) and set(40) put exactly 3 and 40 in the set");
    check(s.count() == 2, "count() is 2");
    check(s.lowest_set() == 3, "lowest_set() is 3");
    s.set(3);
    check(s.count() == 2, "setting 3 again changes nothing");
    s.reset(3);
    check(!s.test(3) && s.lowest_set() == 40, "after reset(3) the smallest number is 40");
    s.set(63);
    check(s.test(63) && s.count() == 2, "63, the highest bit, works too");
    std::println("{} of 7 checks failed", failures);
    return failures == 0 ? 0 : 1;
}

This is what the file prints before you start: every check fails.

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined bitset64.cpp -o bitset64 && ./bitset64
""")

$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined bitset64.cpp -o bitset64 && ./bitset64
FAILED  a new set is empty
FAILED  set(3) and set(40) put exactly 3 and 40 in the set
FAILED  count() is 2
FAILED  lowest_set() is 3
FAILED  setting 3 again changes nothing
FAILED  after reset(3) the smallest number is 40
FAILED  63, the highest bit, works too
7 of 7 checks failed
[exit status 1]

First hint: build the mask for number i from a 64-bit one, std::uint64_t{1} << i. With 1u << i, the check for 40 fails, and UndefinedBehaviorSanitizer reports a shift exponent too large for a 32-bit type. For lowest_set(), think about what std::countr_zero returns for a set that is not empty.

Self-check

Interview questions

Why do C++ programmers use unsigned types for bit manipulation? Unsigned types make every bitwise operation mean exactly its bit pattern. Arithmetic on them wraps modulo 2ⁿ instead of overflowing, >> always shifts in zeros, and the <bit> functions accept only unsigned types. With signed types, ~ and shifts produce negative numbers, >> copies the sign bit, and before C++20 left shifts of negative values were undefined behaviour. Types narrower than int are promoted to int first, so std::uint32_t or std::uint64_t is the safe choice for masks.

Key takeaways

• &, |, ^ and ~ decide each bit of the result from the bits in the same position; << and >> move bits.
• Types narrower than int are promoted to int before any of these operators, so ~ on a byte gives a negative int and << keeps the bits that move past bit 7.
• A shift count must be at least 0 and less than the width of the promoted left operand; anything else is undefined behaviour, reported at run time by -fsanitize=undefined and refused in constant expressions.
• Since C++20, left shifts of signed values keep the low bits of the result, and >> on a negative value rounds down. Unsigned types avoid both questions.
• x & (x - 1) clears the lowest 1 bit and x & -x keeps only it.
• <bit> gives popcount, countr_zero, countl_zero, bit_width, has_single_bit, bit_floor, bit_ceil, rotl, rotr and, in C++23, byteswap; they take unsigned types only and compile to the hardware’s own instructions where there are some.