C++ Reference ยท Algorithms
C++ <bit> header: popcount, countl_zero, rotl and more
Reference for the C++20 <bit> header: popcount, countl_zero, countr_zero, rotl, rotr, bit_width, bit_ceil, bit_floor, has_single_bit, bit_cast, byteswap and endian.
The <bit> header (C++20) gives you portable, well-defined versions of the bit tricks that used to need compiler intrinsics or clever loops: counting set bits, finding leading and trailing zeros, rotating, rounding to powers of two, reinterpreting an object's bytes safely and checking the machine's byte order. Compilers turn most of them into a single CPU instruction.
The counting and rotating functions are templates that accept unsigned integer types only (unsigned char, unsigned short, unsigned, unsigned long, unsigned long long, ...). Passing a signed integer or bool is a compile error, which prevents sign-extension surprises.
#include <bit> std::popcount(0b10110u); // 3 set bits std::countl_zero(1u); // 31 leading zeros for a 32-bit unsigned std::rotl(0b0001u, 3); // 0b1000
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
template<class T> constexpr int std::popcount(T x) noexcept; template<class T> constexpr int std::countl_zero(T x) noexcept; // also countl_one template<class T> constexpr int std::countr_zero(T x) noexcept; // also countr_one template<class T> constexpr T std::rotl(T x, int s) noexcept; // also rotr template<class T> constexpr bool std::has_single_bit(T x) noexcept; template<class T> constexpr T std::bit_ceil(T x); // smallest power of two >= x template<class T> constexpr T std::bit_floor(T x) noexcept; // largest power of two <= x template<class T> constexpr int std::bit_width(T x) noexcept; // 0 for 0, else floor(log2 x) + 1 template<class To, class From> constexpr To std::bit_cast(const From& from) noexcept; template<class T> constexpr T std::byteswap(T x) noexcept; // C++23 enum class std::endian { little, big, native };
| Name | Description |
|---|---|
x |
An unsigned integer (any width). byteswap also accepts signed integers. |
s |
Rotation count. Negative values rotate in the other direction; counts are taken modulo the bit width. |
From / To |
For bit_cast: trivially copyable types of equal size. |
Returns: the counts as int; the rotate, floor/ceil and byteswap functions return T; has_single_bit returns bool; bit_cast returns an object of type To with the same bit pattern.
Errors / undefined behavior: bit_ceil(x) is undefined if the result does not fit in T (for example bit_ceil(0x80000001u)). In a constant expression this is a compile error. bit_cast fails to compile unless both types are trivially copyable and the same size.
Usage notes
- Unsigned only.
std::popcount(-1)does not compile. Cast first (std::popcount(static_cast<unsigned>(x))) and decide consciously what you mean by the sign bit. - Types smaller than
int. The functions operate on the exact type you pass, socountl_zero(std::uint8_t{1})is 7, not 31. The promotion rules of the~and<<operators on small types can still bite in surrounding code. - Zero input.
countl_zero(0)andcountr_zero(0)return the width of the type (socountr_zero(0u)is 32).bit_width(0)is 0.bit_floor(0)is 0.bit_ceil(0)is 1. - Performance. On x86 and ARM,
popcount,countl_zero,countr_zeroand rotations compile to a single instruction when the target supports it. Add-mpopcnt/-march=nativeto enablepopcnton x86; otherwise the compiler emits a short fallback sequence. bit_castreplaces type punning. Reading afloatthrough aunionorreinterpret_cast<uint32_t*>is undefined (or implementation-specific);bit_castis defined and optimizes to a register move. It copies, so it does not alias.- Endianness.
std::endian::nativeislittleon x86-64 and most ARM systems. Use it withif constexprto choose between code paths, andbyteswapto convert between network (big-endian) and host order. bit_ceilfor sizes. It rounds a capacity up to a power of two, the building block of hash tables and ring buffers.- Related classes.
std::bitsetstores many bits and hascount()(which is the same aspopcount) and shifts;<bit>works on single machine words.