std::bitset

Overview

std::bitset<N> packs N bits into one or more machine words. The size is a compile-time constant: you cannot grow or shrink it at runtime. In return you get zero heap allocation, no UB from shifting past a word boundary, and a named API that replaces manual bit twiddling.

Bits are indexed 0 = least significant — bit 0 is the rightmost character when printed. This is the single most common source of confusion: bitset<8>(1).to_string() is "00000001", not "10000000".

Since C++23, the majority of bitset member functions are constexpr.

When to prefer bitset over alternatives:

Prefer bitset over a uint64_t bitmask when N > 64 or when named operations make intent clearer. Prefer it over vector<bool> when N is fixed at compile time. When N is only known at runtime, reach for boost::dynamic_bitset or a vector<uint64_t> with manual masking.

Syntax

Construction

#include <bitset>

std::bitset<8> a;                         // all-zero (default)
std::bitset<8> b(0b10110100);             // from binary literal (C++14)
std::bitset<8> c(0xB4);                   // equivalent hex literal
std::bitset<4> d(255);                    // only low N bits used → 1111

// String constructor — throws std::invalid_argument on any non-zero/one char
std::bitset<8> e("10110100");             // direct string literal
std::bitset<8> f(std::string("10110100"));

// Substring form: (string, pos, count)
std::string s = "XX1010XX";
std::bitset<4> g(s, 2, 4);               // reads chars [2..5] → "1010"

// Custom zero/one characters
std::bitset<4> h("abba", 4, 'a', 'b');   // 'a'→0, 'b'→1 → 0110

Access and queries

std::bitset<8> b(0b10110101);

bool v1 = b[3];          // no bounds check — UB on write if pos >= N
bool v2 = b.test(3);     // throws std::out_of_range if pos >= N

b.count();   // popcount: number of set bits
b.size();    // N — constexpr since C++23
b.any();     // true  if at least one bit is set
b.all();     // true  if all bits are set
b.none();    // true  if no bits are set

Modification

std::bitset<8> b;

b.set();          // all bits → 1
b.reset();        // all bits → 0
b.flip();         // invert all bits

b.set(3);         // bit 3 → 1
b.reset(3);       // bit 3 → 0
b.flip(3);        // bit 3 toggled
b.set(5, false);  // set(pos, value) — bit 5 → 0

Bitwise operators

All standard operators work between two bitset<N> values of the same N:

std::bitset<8> a(0b11001100), b(0b10101010);

auto c = a & b;   // AND  → 10001000
auto d = a | b;   // OR   → 11101110
auto e = a ^ b;   // XOR  → 01100110
auto f = ~a;      // NOT  → 00110011
auto g = a << 2;  // left shift  → 00110000
auto h = a >> 2;  // right shift → 00110011

a &= b; a |= b; a ^= b; a <<= 1; a >>= 1;  // compound forms

Conversion

std::bitset<16> b(0xDEAD);

unsigned long      ul  = b.to_ulong();   // throws std::overflow_error if high bits set and N > 32
unsigned long long ull = b.to_ullong();  // C++11 — safe for N <= 64
std::string        s   = b.to_string();              // "1101111010101101"
std::string        sx  = b.to_string('.', 'X');      // custom zero/one chars

Examples

Permission flags with a scoped enum

enum class Perm : std::size_t { Read = 0, Write = 1, Exec = 2, Admin = 3 };

auto idx = [](Perm p) { return static_cast<std::size_t>(p); };

std::bitset<4> perms;
perms.set(idx(Perm::Read));
perms.set(idx(Perm::Write));

if (perms.test(idx(Perm::Write)))  std::puts("can write");
if (!perms.test(idx(Perm::Exec)))  std::puts("cannot execute");

perms.reset(idx(Perm::Write));     // revoke write
perms.flip(idx(Perm::Admin));      // toggle admin

Sieve of Eratosthenes

bitset is the canonical container for a memory-efficient sieve. One bit per candidate costs ~125 KB for 1 million numbers, versus ~1 MB for vector<bool> (heap-allocated) or ~4 MB for vector<int>.

#include <bitset>
#include <iostream>

constexpr int LIMIT = 1'000'000;
static std::bitset<LIMIT + 1> is_prime;   // static: ~125 KB — too large for a stack frame

void sieve() {
    is_prime.set();
    is_prime.reset(0);
    is_prime.reset(1);

    for (int i = 2; i * i <= LIMIT; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= LIMIT; j += i)
                is_prime.reset(j);
        }
    }
}

int main() {
    sieve();
    std::cout << is_prime.count() << '\n';  // 78498
}

Iterating set bits

bitset has no iterator. Three approaches, in order of portability:

std::bitset<64> b(0b10110101001100ULL);

// Approach 1: simple loop — always portable, O(N)
for (std::size_t i = 0; i < b.size(); ++i)
    if (b[i]) process(i);

// Approach 2: portable for N <= 64 — O(k) where k is the number of set bits
unsigned long long val = b.to_ullong();
while (val) {
    int pos = __builtin_ctzll(val);   // GCC/Clang; MSVC: _BitScanForward64
    process(pos);
    val &= val - 1;                   // clear lowest set bit
}

// Approach 3: libstdc++ extension — fast but non-standard, do not use in portable code
for (std::size_t i = b._Find_first(); i < b.size(); i = b._Find_next(i))
    process(i);

Best Practices

Use test() at trust boundaries. operator[] skips bounds checking even in debug builds. Prefer test() when the index comes from external input; use operator[] only in performance-critical inner loops with a provably valid index.

Declare large bitsets at namespace scope or static. The stack is typically 1–8 MB. bitset<8'000'000> is 1 MB as a local variable and will overflow the stack silently on most platforms. Namespace scope or static local storage is the right home for any bitset over ~64 KB.

Prefer to_ullong() over to_ulong(). On Windows, unsigned long is 32 bits; to_ulong() throws std::overflow_error for N > 32 with any high bit set. to_ullong() (C++11) handles up to N = 64 safely.

Round N to a multiple of 64 when practical. Compilers implement bitset as an array of unsigned long (typically 64-bit). bitset<65> occupies two words and pays for partial-word masking on every operation; bitset<64> occupies one. If you have flexibility in N, favor multiples of 64.

Common Pitfalls

auto x = b[i] captures a proxy, not bool. operator[] returns std::bitset::reference, a proxy object that holds a pointer into the bitset. auto val = b[i] gives you that proxy. If the bitset is then modified or destroyed, the proxy reflects the new state or dangles. Always write bool val = b[i] or auto val = static_cast<bool>(b[i]).

Bit 0 is rightmost, not leftmost. bitset<8>(1) prints as "00000001". When initializing from an integer or indexing by position, remember that index 0 corresponds to the least-significant bit and the rightmost print character.

String constructor throws on unexpected characters. The string constructor throws std::invalid_argument if it encounters any character that is not the designated zero or one character. A space, a newline, or a digit other than 0/1 will throw. Sanitize before constructing from user input.

to_ulong() / to_ullong() throw on overflow at runtime. There is no compile-time protection. A bitset<128> with bit 64 set will throw std::overflow_error from to_ullong() — at runtime, potentially in production. Guard with a size check or mask the upper portion before converting.

Construction In Depth

String constructor: rightmost character is bit 0

The string constructor maps character positions to bit positions in reverse: the last character of the string becomes bit 0 (LSB), and the first character becomes bit N-1 (MSB). This mirrors the conventional left-to-right reading order for binary numbers.

// "10110101" — left char is MSB, right char is bit 0
std::bitset<8> b("10110101");
// b[0] == 1  (rightmost char '1')
// b[7] == 1  (leftmost  char '1')
// b.to_ulong() == 0b10110101 == 181

The integer constructor stores the value in the same bit positions — bit 0 holds the integer's LSB — so these two produce identical bitsets:

std::bitset<8> from_str(  "10110101");   // string constructor
std::bitset<8> from_int(0b10110101);     // integer constructor (C++14 binary literal)
assert(from_str == from_int);            // always true

The integer constructor silently truncates: only the low N bits of the argument are used. This is well-defined, not UB:

std::bitset<4> low4(0xFF);  // 0xFF & 0x0F → 1111
std::bitset<4> also(255);   // same result

Custom zero/one characters (C++11)

The four-argument form (str, pos, n, zero, one) lets you parse non-binary text:

// Parse a string where 'T'=true=1 and 'F'=false=0
std::string flags = "TTFFTFTF";
std::bitset<8> b(flags, 0, 8, 'F', 'T');
// Equivalent to bitset<8>("11001010") — rightmost char still maps to bit 0

// Parse a run-length-free format where '.'=0 and '#'=1
std::bitset<6> mask("##..#.", 6, '.', '#');

Any character that is neither zero nor one (including whitespace) causes std::invalid_argument to be thrown. Always sanitize external input before passing it to the string constructor.

Bitwise Operators In Depth

All bitwise operators require both operands to be bitset<N> of the same N — this is enforced at compile time, which prevents mixing incompatible masks silently.

Shift semantics

Shifting a bitset always produces a new bitset<N> of the same size. Bits shifted out are discarded; zeros are shifted in from the vacated end. There is no rotation operator.

std::bitset<8> b(0b00001111);

auto left2  = b << 2;  // 0b00111100 — bits shifted toward MSB; zeros enter at LSB
auto right3 = b >> 3;  // 0b00000001 — bits shifted toward LSB; zeros enter at MSB

// In-place versions modify the bitset directly
b <<= 1;   // b == 0b00011110
b >>= 2;   // b == 0b00000111

Shifting by N or more produces an all-zero bitset (not UB — this differs from shifting a raw integer, where shifting by >= width is undefined behavior):

std::bitset<8> b(0xFF);
auto zero = b << 8;    // defined: all zeros — not UB
auto also = b >> 100;  // also defined: all zeros

Compound vs. non-compound forms

The compound operators (&=, |=, ^=, <<=, >>=) modify the bitset in place and return a reference to *this. The non-compound binary operators (&, |, ^, <<, >>) return a new bitset by value. For large N (thousands of bits), prefer the compound forms to avoid copying.

std::bitset<1024> a, b;
a &= b;       // no copy — modifies a in place, O(N/w)
auto c = a & b;  // allocates a new bitset<1024> on the stack — still O(N/w) but copies

Conversion Functions: Overflow and Safety

to_ulong() and to_ullong() overflow rules

Both functions throw std::overflow_error if any bit above the target type's width is set. The check is purely about set bits, not about N alone:

std::bitset<128> b;

b.set(0);          // only bit 0 set
auto v = b.to_ullong();  // OK — fits in 64 bits, returns 1ULL

b.set(64);         // now bit 64 is also set
b.to_ullong();     // throws std::overflow_error — bit 64 cannot fit in unsigned long long

// Safe pattern: check before converting
if (b.to_string().find('1', 0) == std::string::npos || /* manual check */ false) { ... }

// Better safe pattern for large bitsets: mask before converting
std::bitset<128> low64_mask;
for (int i = 0; i < 64; ++i) low64_mask.set(i);
auto safe = (b & low64_mask).to_ullong();  // never throws — high bits cleared

On Windows, unsigned long is 32 bits, making to_ulong() throw for any bitset<N> with N > 32 and any bit above position 31 set. Prefer to_ullong() for portability.

to_string() for human-readable output

to_string() always succeeds and never throws. The first character of the result is always the MSB (bit N-1):

std::bitset<8> b(0b10110101);
std::string s = b.to_string();             // "10110101"
std::string custom = b.to_string('_', 'X'); // "X_XX_X_X" — zero='_', one='X'

This is useful for logging, debugging, and serialization to text formats. For binary serialization, convert to unsigned long long or copy words directly.

Query Operations and Complexity

count(), any(), all(), and none() all operate in O(N/w) time, where w is the machine word size (typically 64 bits). They iterate over the internal array of words, not over individual bits.

std::bitset<64> b(0b10110101);

b.count();  // 5 — number of set bits (popcount)
b.any();    // true  — at least one set bit
b.all();    // false — not all bits set
b.none();   // false — has at least one set bit

Hardware popcount

Most standard library implementations use the hardware POPCNT instruction (SSE4.2 / ARMv8) for count() internally, making it extremely fast in practice even for large N. On x86-64 with GCC or Clang, bitset<64>::count() typically compiles to a single popcnt instruction. For very large bitsets (N in the thousands), the loop over words is still fast because each word contributes a single hardware popcnt.

You can verify the compiler output with a simple example on Compiler Explorer: bitset<64>(x).count() compiles to popcnt rax, rdi with -O2.

Short-circuit behavior

any() and none() may short-circuit in theory but most implementations scan all words to avoid branch mispredictions. all() similarly scans all words. Do not expect early-exit behavior for performance-critical code.

std::bitset vs std::vector<bool> vs uint64_t

Both std::bitset<N> and std::vector<bool> pack one bit per element, but they trade off differently across several axes.

The std::vector<bool> proxy reference problem

std::vector<bool> is a notorious special case in the C++ standard. Because it stores bits instead of bool bytes, operator[] cannot return a bool& — there is no such thing as a reference to a single bit in C++. Instead it returns a proxy object (std::vector<bool>::reference) that holds a pointer to the containing word and a bit offset.

This breaks generic code silently:

std::vector<bool> v = {true, false, true};

auto x = v[0];           // x is vector<bool>::reference, NOT bool
bool y = v[0];           // OK — explicit bool conversion
auto z = static_cast<bool>(v[0]);  // OK — explicit

// Breaks with templates:
template<typename T>
void swap_bits(T& a, T& b) { T tmp = a; a = b; b = tmp; }

swap_bits(v[0], v[1]);   // may silently fail — tmp is a proxy, not a bool

std::bitset avoids this trap for operator[] on a non-const bitset only partially — it also returns a proxy (std::bitset::reference) — but because bitset does not pretend to be a sequence container and provides no range-based iteration, the problem surfaces far less often in practice.

Comparison table

When to use each

Use uint64_t (or unsigned int / unsigned char) when you have 64 or fewer flags, need register-level speed, or want full control. Use std::popcount (C++20, <bit>) to count set bits. This is the fastest option for small, fixed-width masks.

Use std::bitset<N> when N exceeds 64, N is fixed at compile time, you want a named API (set, reset, flip, test, count, any, all, none), or you need the safety of no-UB shift semantics. It excels at whole-bitset operations — a bitset<1024> &= other operates on 16 64-bit words in a tight loop.

Use std::vector<bool> only when the number of bits is unknown at compile time and you need STL algorithm compatibility (accepting the proxy limitations). Prefer std::vector<char> or std::vector<uint8_t> if element-by-element access speed matters more than memory.

Use boost::dynamic_bitset when the size is runtime-determined and you need efficient set-bit iteration via find_first()/find_next(), which bitset lacks.

Practical Patterns

Permission bitmask with named positions

Combine a scoped enum with a bitset to get self-documenting, type-safe flags without the overhead of a heap-allocated map:

#include <bitset>

enum class Cap : std::size_t {
    Read   = 0,
    Write  = 1,
    Exec   = 2,
    Admin  = 3,
    Audit  = 4,
    _Count = 5   // sentinel — keep last
};

using Caps = std::bitset<static_cast<std::size_t>(Cap::_Count)>;

inline Caps grant(Caps c, Cap p) {
    c.set(static_cast<std::size_t>(p));
    return c;
}

inline bool can(Caps c, Cap p) {
    return c.test(static_cast<std::size_t>(p));
}

// Usage:
Caps user;
user = grant(user, Cap::Read);
user = grant(user, Cap::Write);

if (can(user, Cap::Exec))   std::puts("can execute");
if (!can(user, Cap::Admin)) std::puts("not admin");

// Serialize to uint8_t for storage (safe: N=5 fits in 8 bits)
uint8_t stored = static_cast<uint8_t>(user.to_ulong());

Billion-bit sieve: memory layout matters

For a prime sieve up to one billion, a bitset uses approximately 119 MB (1e9 / 8 bytes), while vector<int> would need ~3.7 GB. Because bitset must be declared static or at namespace scope for sizes this large (stack is typically 1–8 MB), and because it cannot be heap-allocated with new easily, the canonical pattern is:

#include <bitset>
#include <cstdio>

// ~119 MB — must be static or namespace-scope; never a local variable
static std::bitset<1'000'000'001> is_prime;

void build_sieve(long long limit) {
    is_prime.set();           // mark all as potentially prime
    is_prime.reset(0);
    is_prime.reset(1);

    for (long long i = 2; i * i <= limit; ++i) {
        if (is_prime[i]) {
            for (long long j = i * i; j <= limit; j += i)
                is_prime.reset(j);
        }
    }
}

int main() {
    build_sieve(1'000'000'000LL);
    std::printf("%zu primes up to 1e9\n", is_prime.count());  // 50,847,534
}

For comparison, the same sieve with vector<bool> would require a heap allocation and would be similarly fast for the sieve itself, but bitset's whole-set set() (which sets all bits in a loop over words) is typically faster than the vector<bool> equivalent because bitset can use a fill of ~0ULL per word without branch overhead.

Choosing based on N and dynamism

// N <= 64, fixed: raw integer — fastest
uint64_t flags = 0;
flags |= (1ULL << 3);          // set bit 3
bool b = (flags >> 3) & 1;     // test bit 3
int  c = __builtin_popcountll(flags);  // GCC/Clang; std::popcount in C++20

// N <= 64 but want named ops: bitset<64>
std::bitset<64> mask(flags);
mask.set(7);
std::size_t cnt = mask.count();

// 64 < N <= compile-time constant: bitset<N>
std::bitset<256> large_mask;
large_mask.set(200);

// N only known at runtime: dynamic options
// Option A: std::vector<bool>  — STL algorithms, proxy refs, heap
// Option B: std::vector<uint64_t> with manual masking — fastest random access
// Option C: boost::dynamic_bitset — named ops + find_first/find_next

See Also

• std::vector<bool> — dynamically sized bit sequence; heap-allocated, slower element access, no bitwise operators across the whole set
• std::popcount — C++20 hardware popcount for unsigned integer types, from <bit>
• Bit manipulation utilities — <bit> — C++20: std::countl_zero, std::countr_zero, std::rotl, std::rotr, std::has_single_bit
• boost::dynamic_bitset — runtime-sized bitset with find_first()/find_next() for efficient set-bit iteration