Skip to content
Tutorials Center
My learning

Topics

Lesson 104 of 171 ยท The Standard Library (STL)

std::bitset

Learn C++ std::bitset - fixed-size bit sets, set, reset, flip and test, count, any, all and none, bitwise operators, to_string and to_ulong, plus real use cases.

A std::bitset<N> (header <bitset>) is a fixed-size sequence of N bits that you can read and change one at a time, or all at once with the familiar bitwise operators. Think of it as an unsigned integer with a size you choose, named operations instead of mask arithmetic, bounds-checked access when you want it, and a readable string form for debugging.

You already used the raw tools in Bitwise Operators: x |= 1u << 5 to set a bit, x & mask to test one. Those work, but they're easy to get subtly wrong (shifting by the width of the type is undefined behavior, 1 << 31 overflows a signed int) and hard to read. In this lesson you'll create bitsets from numbers and strings, learn which end is bit 0, set and test individual bits, count them, combine bitsets with &, |, ^ and shifts, convert back to strings and integers, and see where a bitset is the right tool and where it isn't.

Creating a bitset

The size N is a template argument, so it's fixed at compile time. Every bitset starts out all zeros unless you give it an initial value. You can initialize one from an unsigned long long or from a string of '0' and '1' characters.

C++ Creating bitsets and reading their size

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.

Two details trip up almost everyone:

  • Bit 0 is the rightmost bit. The string form is written like a binary number, most significant bit first, so "10100101"[0] is bit 7, not bit 0. When you index with b[0], you get the last character of to_string().
  • Extra bits are silently dropped. std::bitset<4>{0xFF} keeps only the low four bits. That's convenient for masks but can hide a mistake.

If the string contains a character that isn't the "zero" or "one" character, the constructor throws std::invalid_argument. The size isn't checked against the string length: a shorter string fills only the low bits, and a longer one uses only its first N characters.

Since C++23, almost all std::bitset members are constexpr, so you can build and query bitsets at compile time too. The constructor from unsigned long long has been constexpr since C++11.

Reading and changing single bits

A bitset gives you named operations for every bit-twiddling idiom:

Operation Effect Raw-integer equivalent
b.set(i) bit i becomes 1 x |= 1u << i
b.set(i, value) bit i becomes value (two cases)
b.reset(i) bit i becomes 0 x &= ~(1u << i)
b.flip(i) bit i is inverted x ^= 1u << i
b.test(i) true if bit i is 1 (x >> i) & 1
b[i] read or assign bit i, no bounds check
b.set(), b.reset(), b.flip() all bits at once x = ~0u, x = 0, x = ~x

set, reset, flip and test check the index and throw std::out_of_range if i >= N. operator[] doesn't check: an out-of-range index is undefined behavior, just as with std::vector. The mutating functions return *this, so calls can be chained.

C++ set, reset, flip and test

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.

Notice b[4] = true. A single bit has no address, so operator[] can't return a bool&. Instead it returns a small proxy object, std::bitset<N>::reference, that remembers which bit it refers to and turns assignments into bit operations. The proxy also has flip() and converts to bool. That's why auto x = b[1]; gives you a proxy, not a bool: copy it into a bool explicitly if you need a value that won't change when the bitset does.

Counting and asking about all bits

Questions about the whole set are single calls:

  • b.count() returns how many bits are 1 (a "population count").
  • b.any() is true if at least one bit is 1, b.none() if none are, and b.all() if all are.
  • b.size() returns N.

These are implemented with fast word-at-a-time instructions, so count() on a std::bitset<1024> touches only 16 machine words, not 1,024 bits.

Here's a realistic example: tracking which letters appear in a word. Each of the 26 bits stands for one letter. Two words share a letter exactly when the & of their sets has any bit set, and a word is a pangram when all 26 bits are on.

C++ Letter sets with count, any, all and none

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.

This style replaces whole loops with single operations. Comparing two words for shared letters is one & plus one any(), no matter how long the words are.

Bitwise operators on whole bitsets

Bitsets of the same size support every bitwise operator you know from integers:

  • a & b, a | b, a ^ b and the compound forms &=, |=, ^=.
  • ~a inverts all bits.
  • a << n and a >> n shift, filling with zeros. Shifting by N or more simply gives all zeros; unlike integer shifts, it's never undefined behavior.
  • a == b and a != b compare all bits. There is no <, so bitsets can't be keys of a std::map without a custom comparator. They do have a std::hash specialization, so std::unordered_set<std::bitset<N>> works.

Bitsets of different sizes don't mix: std::bitset<8>{} & std::bitset<16>{} doesn't compile. That's a feature. It catches the "wrong mask for this field" bug at compile time.

C++ Permissions with bitwise operators

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.

The test (editor & viewer) == viewer reads as "every permission the viewer has, the editor has too", which is the subset check. The unscoped enum with an explicit std::size_t underlying type gives readable bit names that convert to indexes automatically. With an enum class you'd write std::to_underlying(Permission::Read) instead (see Enumerations).

Converting to strings and integers

You've already used to_string(). It accepts optional "zero" and "one" characters, as in to_string('.', '#'), which is handy for drawing. To get a number back, use:

  • to_ulong(), which returns unsigned long.
  • to_ullong(), which returns unsigned long long.

Both throw std::overflow_error if a bit that doesn't fit in the result type is set. A std::bitset<100> with only low bits set converts fine; one with bit 80 set doesn't.

Streams work too: std::cout << b prints the same characters as to_string(), and std::cin >> b reads up to N characters of 0 and 1. There's no std::formatter for std::bitset in C++23 (C++26 adds one), so with std::println call to_string() yourself, or format the integer with {:b}.

C++ to_string, to_ulong and overflow_error

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.

The last part fails on purpose: bit 80 can't be represented in a 64-bit unsigned long long, so to_ullong() throws instead of silently losing data.

A classic use: the sieve of Eratosthenes

A bitset shines when you need one yes/no answer for each of many small integers. The sieve of Eratosthenes finds primes by crossing out multiples: start with all numbers marked "maybe prime", and for each prime p, mark p*p, p*p + p, โ€ฆ as composite. A std::bitset<1'000'001> holds a flag for every number up to a million in about 122 KB, one-eighth of a bool array.

C++ Sieve of Eratosthenes with a bitset

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.

The prime count is size() - count(): everything that wasn't crossed out. The bitset is declared static (at namespace scope it would be anyway), because putting large objects in a local variable risks a stack overflow; see Memory Layout.

bitset, integers, vector<bool> or something else?

std::bitset isn't the only way to store bits. Choose by asking two questions: is the size known at compile time, and do you need integer arithmetic?

Tool Size Best for
std::bitset<N> fixed at compile time, any N flags, masks, sieves, small sets of integers, readable bit code
unsigned integer + <bit> 8 to 64 bits hardware registers, hashing, performance-critical code needing std::popcount, std::countr_zero, std::rotl
std::vector<bool> chosen at run time, can grow large dynamic bit arrays (beware its proxy quirks, see std::vector in Depth)
enum class with operators small, fixed type-safe flag APIs with named values
std::set<int> / std::unordered_set<int> dynamic, sparse few values from a huge range

A few more facts help with the decision:

  • There are no iterators. std::bitset isn't a container: no begin()/end(), so no range-for and no STL algorithms. Loop over indexes 0 โ€ฆ size() - 1 instead.
  • There's no "find first set bit" in the standard bitset (GCC has a non-standard _Find_first). If you need that, use an integer with std::countr_zero.
  • sizeof rounds up to whole words. On our 64-bit compiler sizeof(std::bitset<1>) is 8 bytes, and std::bitset<65> is 16.
  • It's a value type. Copying a bitset copies all its bits; comparing compares all of them.

Common mistakes

  • Reading bits in string order. b.to_string()[0] is the highest bit, b[0] is the lowest. When parsing a string like "1000", bit 3 is set, not bit 0.
  • Using operator[] with an unchecked index. Prefer test() when the index comes from input.
  • Expecting to_ulong() to truncate. It throws std::overflow_error when high bits are set; mask first if truncation is what you want.
  • Wanting a run-time size. std::bitset<n> with a variable n doesn't compile. Use std::vector<bool> or a std::vector<std::uint64_t> you manage yourself.
  • Mixing up count() and size(). count() is the number of ones; size() is N.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. std::bitset<4> b{"1000"}; Which call returns true?

    The string is written most significant bit first, so its first character is bit 3 and its last character is bit 0. Only bit 3 is set.
  2. 2. std::bitset<8> b{0b0000'1111}; b.flip(0); b.reset(3); b.set(7); What is b.to_string()?

    Starting from 00001111, flipping bit 0 gives 00001110, resetting bit 3 gives 00000110, and setting bit 7 gives 10000110.
  3. 3. What happens when you call b.test(10) on a std::bitset<8>?

    test, set, reset and flip check their index and throw std::out_of_range. Only operator[] is unchecked.
  4. 4. Given std::bitset<5> need{"00101"} and std::bitset<5> have{"01101"}, which expression is true exactly when have contains every bit of need?

    Intersecting with need keeps only need's bits; if all of them survive, the result equals need. Here that's 00101 == 00101, so it's true.
  5. 5. std::bitset<128> b; b.set(100); What does b.to_ullong() do?

    to_ulong and to_ullong refuse to lose data. Any set bit above the result type's width makes them throw std::overflow_error.

Summary

  • std::bitset<N> from <bitset> is a fixed-size, compile-time-sized set of bits, initialized from an integer or a '0'/'1' string; bit 0 is the rightmost character.
  • set, reset, flip and test change and read single bits with bounds checks; operator[] is unchecked and returns a proxy.
  • count, any, all, none and size answer questions about all bits at once, using fast word-sized operations.
  • &, |, ^, ~, <<, >>, == work on bitsets of the same size; shifting past the size gives zeros, not undefined behavior.
  • to_string (with custom characters), to_ulong and to_ullong convert back; the integer conversions throw std::overflow_error instead of truncating.
  • Use bitsets for flags, masks, sieves and small integer sets; use integers with <bit> for raw performance, and std::vector<bool> when the size is only known at run time.

Next: Lambda Expressions, the short inline functions that make every STL algorithm easy to customize.