# Bit manipulation

> C++20 gave bits a real library in the header bit, and it also pinned down shifts on signed numbers. The traps that remain are shift counts, integer promotion on small types, and the preconditions of a few functions.

- **Source:** C++ Atlas (https://cppatlas.com/topics/bit-manipulation)
- **Track:** Library utilities
- **Estimated reading time:** 13 minutes
- **ISO C++ clauses:** [bit] (https://eel.is/c++draft/bit), [bit.cast] (https://eel.is/c++draft/bit.cast), [bit.byteswap] (https://eel.is/c++draft/bit.byteswap), [bit.endian] (https://eel.is/c++draft/bit.endian), [bit.pow.two] (https://eel.is/c++draft/bit.pow.two), [bit.rotate] (https://eel.is/c++draft/bit.rotate), [bit.count] (https://eel.is/c++draft/bit.count), [expr.shift] (https://eel.is/c++draft/expr.shift), [expr.unary.op] (https://eel.is/c++draft/expr.unary.op), [conv.prom] (https://eel.is/c++draft/conv.prom), [class.bit] (https://eel.is/c++draft/class.bit), [support.types.byteops] (https://eel.is/c++draft/support.types.byteops)
- **cppreference links:** [Bit manipulation (header bit)](https://en.cppreference.com/w/cpp/header/bit), [std::bit_cast](https://en.cppreference.com/w/cpp/numeric/bit_cast), [std::popcount](https://en.cppreference.com/w/cpp/numeric/popcount), [std::bit_ceil](https://en.cppreference.com/w/cpp/numeric/bit_ceil), [std::rotl](https://en.cppreference.com/w/cpp/numeric/rotl), [std::byteswap](https://en.cppreference.com/w/cpp/numeric/byteswap), [std::endian](https://en.cppreference.com/w/cpp/types/endian), [Arithmetic operators (shift operators)](https://en.cppreference.com/w/cpp/language/operator_arithmetic), [std::byte](https://en.cppreference.com/w/cpp/types/byte), [Bit-field](https://en.cppreference.com/w/cpp/language/bit_field)
- **Prerequisites:** fundamental-types-and-arithmetic-conversions, strict-aliasing-and-undefined-behavior

## The one idea

Bit work in C++ goes wrong in three places: the operand is narrower than `int` and gets promoted, the shift count is out of range, or the function has a precondition that nobody read. The `<bit>` header, added in C++20, removes most of the hand-written loops and compiler intrinsics. What is left are those three traps.

> **Mental model.** Treat every integer as a fixed-width row of bits, but remember that arithmetic and shifts first widen anything smaller than `int` to `int`. The `<bit>` functions skip that step: they look at the width of the exact type you pass.

Since C++20 the language also says that signed integers use two's complement. That is why the rules for shifting signed values could finally be written as plain arithmetic.

## What `<bit>` offers

The counting and rotating functions work on unsigned integer types only: `unsigned char`, `unsigned short`, `unsigned int`, the longer unsigned types, and extended unsigned types. They do not accept signed types, plain `char`, `bool`, `char8_t`, `char16_t`, `char32_t` or `wchar_t`. Calling `std::popcount(1)` is rejected at compile time because `1` is an `int`.

```cpp
#include <bit>
#include <cstdint>
#include <cstdio>

int main() {
  std::printf("%d\n", std::popcount(0b1011u));            // 3
  std::printf("%d\n", std::countl_zero(1u));              // 31 for a 32-bit unsigned int
  std::printf("%d\n", std::countl_zero(std::uint8_t{1})); // 7: the width of uint8_t, not of int
  std::printf("%d\n", std::countr_zero(8u));              // 3
  std::printf("%d\n", std::bit_width(255u));              // 8
  std::printf("%d\n", std::has_single_bit(0u));           // 0: zero is not a power of two
}
```

The second and third lines show the point of the mental model. `countl_zero` counts from the top of the type you gave it, not from the top of an `int`.

`rotl` and `rotr` rotate within the width of the type, and a negative count rotates the other way, so `std::rotl(x, -1)` equals `std::rotr(x, 1)`. Unlike a built-in shift, a rotate count of any value is defined.

```cpp
#include <bit>
#include <cstdint>

static_assert(std::rotl(std::uint8_t{0x81}, 1) == 0x03);
static_assert(std::rotl(std::uint8_t{0x81}, -1) == 0xC0);
static_assert(std::byteswap(std::uint16_t{0x1234}) == 0x3412);  // C++23
```

The power-of-two helpers are `has_single_bit`, `bit_floor`, `bit_ceil` and `bit_width`. `bit_floor(37u)` is 32, `bit_ceil(37u)` is 64, and `bit_width(0u)` is 0. `bit_floor(0)` is 0, and `bit_ceil(0)` is 1.

> **Standardese.** [bit.pow.two] says `bit_ceil(x)` is the smallest power of two not smaller than `x`, and that the behaviour is undefined if that value is not representable in the type. So `bit_ceil(0x80000001u)` is undefined for a 32-bit `unsigned`, and because the function is `constexpr`, constant evaluation rejects the call instead of returning a wrapped value.

`std::byteswap`, added in C++23, reverses the bytes of any integer type, signed ones included. It does not know about endianness. To convert between a wire order and the host order, compare `std::endian::native` against `std::endian::little` or `std::endian::big`. If `native` equals neither, the platform is mixed-endian, which is rare but allowed.

## `bit_cast`

`std::bit_cast<To>(from)` reinterprets the object representation of `from` as a value of type `To`. Both types must have the same size and be trivially copyable, or the call does not compile. It is `constexpr` when neither type contains a pointer, a union, a reference, or a volatile member, which makes it the sanctioned way to look inside a float in a constant expression.

```cpp
#include <bit>
#include <cstdint>

// Assumes IEEE binary32 float and a 32-bit unsigned.
static_assert(std::bit_cast<std::uint32_t>(1.0f) == 0x3f800000u);
// std::bit_cast<float>(std::uint64_t{1});  // ill-formed: sizes differ
```

Unlike `reinterpret_cast`, `bit_cast` creates a new object, so there is no aliasing problem. The `strict-aliasing-and-undefined-behavior` topic explains why `*reinterpret_cast<uint32_t*>(&f)` is not equivalent. If some bit pattern in the source does not correspond to a valid value of `To`, for example when casting arbitrary bytes to `bool`, the behaviour is undefined.

## Shifts: the counts

A shift expression has undefined behaviour when the right operand is negative or is greater than or equal to the width of the promoted left operand. This holds for `<<` and `>>`, signed and unsigned, and it is what makes `1u << 32` undefined for a 32-bit `unsigned`. The result is not zero, and nothing else is promised either.

```cpp
// constexpr unsigned a = 1u << 32;
// ill-formed: shift count >= width, so not a constant expression

constexpr unsigned mask(unsigned n) {
  return n == 0 ? 0u : ~0u >> (32 - n);  // n == 32 gives all ones; 0 must be handled
}
```

The classic form `(1u << n) - 1` for the low `n` bits fails at `n == 32`. Guard the edge cases explicitly, as the function above does for zero.

The type of the result is the promoted type of the left operand alone. The type of the count does not matter.

## Shifts: signedness and promotion

Right shift of a negative signed number was implementation-defined before C++20. Since C++20 it is the arithmetic shift: the result rounds toward negative infinity. That differs from division, which truncates toward zero.

```cpp
#include <cstdio>

int main() {
  std::printf("%d %d\n", -7 >> 1, -7 / 2);  // -4 -3 in C++20 and later
  int a = -1;
  std::printf("%d\n", a << 3);              // -8, well-defined since C++20
}
```

Left shift of a signed value used to be undefined for a negative left operand, and for results that did not fit even in the unsigned counterpart type. Since C++20 the result is the mathematical product reduced modulo 2 to the power of the width, interpreted as signed. So `-1 << 3` is `-8`, and `1 << 31` is `INT_MIN` for a 32-bit `int`. The count rules above still apply.

Integer promotion is the second trap. Each operand of a shift or bitwise operator is promoted separately, so a `std::uint8_t` or `unsigned short` becomes `int` first.

```cpp
#include <cstdint>
#include <cstdio>

int main() {
  std::uint8_t b = 0x0F;
  std::printf("%d\n", ~b);                   // -16, not 240: ~ works on the promoted int
  std::printf("%d\n", ~b == 0xF0);           // 0
  std::printf("%d\n", std::uint8_t(~b));     // 240: convert back to the narrow type
  std::uint8_t c = 0x80;
  std::printf("%d\n", c << 24);              // -2147483648: promoted to int, defined in C++20
}
```

Assume 32-bit `int` for those results. The fix is to convert back to the narrow type after the operation, or to work in `unsigned` throughout. The promotion rules themselves belong to `fundamental-types-and-arithmetic-conversions`.

> **Pitfall.** Shifting a `uint8_t` or `unsigned short` left is not an unsigned operation. The operand is promoted to `int`, so the result of `std::uint8_t{0x80} << 24` is the negative `int` `INT_MIN`, not the unsigned value 2147483648.

## Masks, `std::byte` and bit-fields

For raw memory, `std::byte` is an `enum class : unsigned char` that supports the bitwise operators and shifts but no arithmetic. That stops you adding two bytes by accident. Convert with `std::to_integer<int>(b)`, and build a byte by list-initializing from a constant.

```cpp
#include <cstddef>

constexpr std::byte lo{0x0F};
constexpr std::byte hi = lo << 4;               // 0xF0, and the type stays std::byte
static_assert(std::to_integer<int>(hi) == 240);
static_assert((hi | lo) == std::byte{0xFF});
```

Reading multi-byte values from a buffer is where bit work, promotion and endianness meet. The portable way to decode a big-endian value is with shifts, which give the same answer on every host. Each byte is widened to `std::uint32_t` before it is shifted, because shifting the byte directly would promote it to `int` and push the top byte into the sign bit. When the value is already sitting in an integer in network order, `std::endian::native` selects whether a `std::byteswap` is needed.

```cpp
#include <bit>
#include <cstddef>
#include <cstdint>

constexpr std::uint32_t load_be32(const std::byte* p) {
  return (std::uint32_t(p[0]) << 24) | (std::uint32_t(p[1]) << 16) |
         (std::uint32_t(p[2]) << 8)  |  std::uint32_t(p[3]);
}

constexpr std::uint32_t be_to_host(std::uint32_t v) {  // byteswap is C++23
  if constexpr (std::endian::native == std::endian::little) return std::byteswap(v);
  else return v;
}
```

The first function never mentions endianness, which is the point: arithmetic on values is host-independent, and only the interpretation of raw memory depends on the host.

Bit-fields look convenient, but the order of allocation, whether a field may straddle a storage unit, and how the compiler packs them are implementation-defined. Use them for compact in-memory flags, and use explicit shifts and masks for anything that must match a file format or a protocol. The standard does not promise that two compilers produce the same layout.

## What to remember

- `<bit>` functions need unsigned integer types and look at the width of the exact type; `countl_zero(uint8_t{1})` is 7.
- `bit_ceil` is undefined when the result does not fit, and constant evaluation catches it. `bit_floor(0)` is 0 and `bit_ceil(0)` is 1.
- `rotl` and `rotr` accept any count; a negative count reverses the direction.
- `std::byteswap` is C++23 and works on any integer type; `std::endian` is the way to ask about host order.
- `bit_cast` needs equal sizes and trivially copyable types, works in constant expressions, and avoids the aliasing rules.
- A shift count that is negative or at least the promoted width is undefined, for both directions.
- Since C++20, right shift of a negative number is arithmetic, and left shift of a signed number is modular.
- Operands smaller than `int` are promoted before `~`, `<<`, `>>` and the other bit operators.
- Use `std::byte` for raw bytes, and avoid bit-fields for external formats.

## Concept Map Outline

- **Bit manipulation:** The bit header counts and rotates by exact type width; shifts and promotion are where the surprises live.
  - **Counting and rotating:** These functions take unsigned types only and use the width of the exact type, with no promotion to int.
    - **popcount:** Counts the set bits of an unsigned integer.
    - **countl_zero, countr_zero:** Count leading or trailing zeros in the width of the argument type; countl_zero(uint8_t{1}) is 7.
    - **rotl and rotr:** Rotate within the type width; any count is allowed and a negative count reverses direction.
  - **Power-of-two helpers:** has_single_bit, bit_width, bit_floor and bit_ceil describe a value's relation to powers of two.
    - **has_single_bit:** True only for powers of two, so false for zero.
    - **bit_floor, bit_width:** bit_floor(0) is 0, bit_width(0) is 0, and bit_floor(37u) is 32.
    - **bit_ceil precondition:** Undefined if the result does not fit the type; constant evaluation rejects it.
  - **Reinterpreting bytes:** bit_cast, byteswap and endian handle object representation without aliasing violations.
    - **bit_cast:** Needs equal sizes and trivially copyable types; constexpr unless pointers, unions or references are involved.
    - **byteswap (C++23):** Reverses the bytes of any integer type and knows nothing about the host order.
    - **std::endian:** little, big and native describe byte order; native may equal neither on a mixed-endian platform.
  - **Shift counts:** The right operand has to be within range for both shift directions.
    - **Count out of range:** A negative count or one at least the promoted width is undefined, for signed and unsigned alike.
    - **Result type:** The result has the promoted type of the left operand; the count's type does not matter.
    - **Mask pitfall:** (1u << n) - 1 fails at n equal to the width; guard the edge cases.
  - **Signedness and promotion:** Narrow operands become int before shifts and bitwise operators, and C++20 tightened signed shifts.
    - **Right shift, C++20:** Negative values shift arithmetically, rounding toward negative infinity, so -7 >> 1 is -4.
    - **Left shift, C++20:** Signed left shift is modular and two's complement, so -1 << 3 is -8.
    - **Promotion trap:** ~uint8_t{15} is the int -16, and uint8_t{0x80} << 24 is a negative int.
    - **Two's complement:** C++20 requires signed integers to use two's complement.
  - **Bytes and bit-fields:** Use std::byte for raw memory and be wary of bit-fields in external formats.
    - **std::byte:** Supports bitwise operators and shifts, no arithmetic; convert with std::to_integer.
    - **Bit-field layout:** Allocation order and straddling are implementation-defined, so use masks for wire formats.

## Standardese Quiz Questions

### Question 1 [warmup] ([bit.pow.two])

In C++20 or later, assuming a 32-bit `unsigned int`, what is printed?

```cpp
#include <bit>
#include <cstdio>

int main() {
  std::printf("%d %d %u %u\n", std::has_single_bit(0u), std::has_single_bit(8u),
              std::bit_floor(37u), std::bit_ceil(37u));
}
```

A. 1 1 32 64
B. 0 0 32 38
C. 0 1 32 64
D. 0 1 37 37

**Answer (C):** 0 1 32 64

**Why:** Zero is not a power of two, so `has_single_bit(0u)` is false, and 8 has a single set bit. `bit_floor(37u)` is the largest power of two not above 37, which is 32, and `bit_ceil(37u)` is the smallest one not below it, which is 64. The option starting with 1 treats zero as a power of two.

### Question 2 [warmup] ([expr.shift], [expr.mul])

In C++20 or later, assuming a 32-bit `int`, what is printed?

```cpp
#include <cstdio>

int main() {
  std::printf("%d %d\n", -7 >> 1, -7 / 2);
}
```

A. -3 -3
B. -4 -3
C. -4 -4
D. -3 -4

**Answer (B):** -4 -3

**Why:** Since C++20, right shift of a negative signed value is the arithmetic shift, which rounds toward negative infinity, so `-7 >> 1` is -4. Division truncates toward zero, so `-7 / 2` is -3. Before C++20 the shift result was implementation-defined, and the tempting `-3 -3` assumes the two operators agree.

### Question 3 [warmup] ([bit.rotate])

In C++20 or later, what is printed?

```cpp
#include <bit>
#include <cstdint>
#include <cstdio>

int main() {
  std::uint8_t x = 0x81;
  std::printf("%d %d\n", std::rotl(x, 1), std::rotl(x, -1));
}
```

A. 258 192
B. 3 3
C. Ill-formed: `rotl` does not accept `std::uint8_t`
D. 3 192

**Answer (D):** 3 192

**Why:** `rotl` rotates within the width of its argument type, which is 8 bits here, so 0x81 rotated left by one is 0x03 because the top bit wraps around. A negative count rotates the other way, so `rotl(x, -1)` is 0xC0, which is 192. The answer 258 treats the operand as an `int` and lets the bit escape.

### Question 4 [tricky] ([bit.count])

In C++20 or later, assuming a 32-bit `unsigned int`, what is printed?

```cpp
#include <bit>
#include <cstdint>
#include <cstdio>

int main() {
  std::printf("%d %d\n", std::countl_zero(std::uint8_t{1}), std::countl_zero(1u));
}
```

A. 31 31
B. 7 7
C. 7 31
D. 8 32

**Answer (C):** 7 31

**Why:** The `<bit>` functions look at the width of the exact type, so `countl_zero(std::uint8_t{1})` counts the seven leading zeros of an 8-bit value, and `countl_zero(1u)` counts 31 of a 32-bit value. Unlike the built-in operators, they do not promote a narrow operand to `int` first, which is why `31 31` is wrong.

### Question 5 [tricky] ([expr.unary.op], [conv.prom])

Assume a 32-bit `int`. What is printed?

```cpp
#include <cstdint>
#include <cstdio>

int main() {
  std::uint8_t b = 0x0F;
  std::printf("%d\n", ~b);
}
```

A. 240
B. -16
C. -241
D. Undefined behavior: `~` overflows

**Answer (B):** -16

**Why:** A `std::uint8_t` operand of `~` is promoted to `int` first, so `~b` complements all 32 bits of the value 15, giving -16. The result is not converted back to 8 bits unless you write `std::uint8_t(~b)`, which is what the tempting answer 240 assumes. There is no overflow, since complementing an `int` is always defined.

### Question 6 [tricky] ([expr.shift])

In C++20, assuming a 32-bit `int`, what does this program print?

```cpp
#include <cstdio>

int main() {
  int a = -1;
  std::printf("%d\n", a << 3);
}
```

A. -8
B. Undefined behavior: the left operand is negative
C. 8
D. Implementation-defined

**Answer (A):** -8

**Why:** Since C++20 a left shift of a signed value is defined modulo 2 to the power of the width, and the two's complement result is read back as signed. For `-1 << 3` that gives -8. Before C++20 a negative left operand made the shift undefined, which is the answer a C++17 reader would give, and it is not a matter of implementation choice now.

### Question 7 [standardese] ([expr.shift], [expr.const])

In C++23, assuming a 32-bit `unsigned int`, what is the status of this declaration?

```cpp
constexpr unsigned x = 1u << 32;

int main() { return 0; }
```

A. Well-formed, and `x` is 0
B. Well-formed, and `x` is 1
C. Ill-formed: the initializer is not a constant expression
D. Well-formed, and `x` has an unspecified value

**Answer (C):** Ill-formed: the initializer is not a constant expression

**Why:** A shift whose count is greater than or equal to the width of the promoted left operand has undefined behaviour, even for unsigned types. Undefined behaviour is never allowed in a constant expression, so initializing a `constexpr` variable this way is ill-formed. Shifting out all the bits to leave zero is a common expectation, and it is not what the language says.

### Question 8 [standardese] ([bit.pow.two], [expr.const])

In C++23, assuming a 32-bit `unsigned int`, what is the status of this program?

```cpp
#include <bit>

static_assert(std::bit_ceil(0x80000001u) == 0);

int main() { return 0; }
```

A. `bit_ceil` returns 0 and the assertion passes
B. `bit_ceil` returns 0x80000000 and the assertion fails
C. `bit_ceil` throws `std::overflow_error`
D. The call has undefined behaviour, so it is not a constant expression and the program is ill-formed

**Answer (D):** The call has undefined behaviour, so it is not a constant expression and the program is ill-formed

**Why:** The next power of two above 0x80000001 would be 2 to the 32nd power, which does not fit in a 32-bit `unsigned int`. [bit.pow.two] makes that case undefined behaviour, and a `constexpr` function may not be used with undefined behaviour in constant evaluation, so the `static_assert` is rejected. Wraparound to 0 is what a hand-written loop would give, but the library function promises nothing of the kind.
