Bitset

Leave a Comment / C++ STL / By

Hi everyone ✋

In this tutorial we will talk about Bitset

So, What is Bitset actually?

Bitset is a container of C++ STL that stores a fixed-size sequence of bits — just 0s and 1s. Think of it as an array of bools, but far more compact and with a whole toolbox of bit-level operations built right in.

The most important thing to understand about bitset is that its size is fixed at compile time. We decide how many bits we want when we declare it, and that number goes inside angle brackets as a template parameter —


// a bitset that holds 8 bits
bitset <8> bits;

This is different from almost every other container we have seen. A vector grows, a set rearranges itself — but a bitset is locked to the size we give it. We cannot push, pop, insert, or erase bits. We can only flip the bits that are already there between 0 and 1.

Why bother with a whole container just for bits? Because it is extremely memory efficient. A normal bool takes one full byte (8 bits) even though it only needs one bit of information. A bitset packs its bits together, so 64 bits take only 8 bytes instead of 64. On top of that, bitset gives us fast bitwise operations and clean, readable functions like set(), count(), and flip() — so we get the speed of raw bit manipulation without the cryptic code.

💡 Note — bitset is not quite a “normal” container — Unlike vector, set, or map, bitset does not provide iterators (no begin() / end()), so we cannot use it with a range-based for loop or STL algorithms. It is really a fixed-width bit array with a convenient interface, not a general-purpose container.

How bits are numbered

Before we go further, one detail trips everyone up. The bits in a bitset are numbered from right to left, starting at position 0. So the rightmost bit is position 0 (the least significant bit), and the leftmost bit is position N-1.


bitset <8> bits("01000101");

//  position:  7 6 5 4 3 2 1 0
//  bit:       0 1 0 0 0 1 0 1

So bits[0] is 1, bits[2] is 1, and bits[6] is 1 — everything else is 0. Keep this in mind, because it matters every time we touch a bit by its position.

Header File Inclusion for bitset

#include <bitset>

Declaration & Initialization

Declaring an empty bitset —

A freshly declared bitset has all its bits set to 0 —


bitset <8> bits;

After this, bits will look like this —

 

0 0 0 0 0 0 0 0

 

Declaring a bitset from an integer —

We can initialize a bitset with an integer, and bitset stores its binary representation —


// 42 in binary is 00101010
bitset <8> bits(42);

After this, bits will look like this —

 

0 0 1 0 1 0 1 0

 

Declaring a bitset from a string —

We can also initialize a bitset from a string of ‘0’s and ‘1’s —


bitset <8> bits("11001010");

The string reads left to right, so the leftmost character becomes the highest-position bit.

💡 Note on size mismatches — If the integer or string has fewer bits than the bitset, the extra high positions are filled with 0. If the value has more bits than the bitset can hold, the extra high bits are simply dropped. The bitset never grows to fit — its size is fixed.

Declaring bitsets of different sizes —

The number in the angle brackets must be a compile-time constant —


bitset <16> flags;
bitset <32> mask;
bitset <64> bigSet;

Setting bits

set() method

set() with no argument turns all bits to 1 —


bitset <8> bits;

bits.set();

// bits is now 11111111

set() with a position

set(pos) turns a single bit (at the given position) to 1 —


bitset <8> bits;

bits.set(0);   // set the rightmost bit
bits.set(3);

// bits is now 00001001

set() with a position and a value

We can also pass a value to set a bit to 1 or 0 explicitly —


bits.set(5, true);    // set bit 5 to 1
bits.set(3, false);   // set bit 3 to 0

Resetting bits

reset() method

reset() with no argument turns all bits to 0 —


bitset <8> bits("11111111");

bits.reset();

// bits is now 00000000

reset() with a position

reset(pos) turns a single bit to 0 —


bitset <8> bits("11111111");

bits.reset(0);   // clear the rightmost bit

// bits is now 11111110

Flipping bits

flip() method

flip() with no argument toggles every bit — every 0 becomes 1 and every 1 becomes 0 —


bitset <8> bits("00001111");

bits.flip();

// bits is now 11110000

flip() with a position

flip(pos) toggles only a single bit —


bitset <8> bits("00001111");

bits.flip(0);   // toggle the rightmost bit

// bits is now 00001110

Accessing a bit

[ ] subscript operator

We can read or write a single bit using the [ ] operator, just like an array. Remember, position 0 is the rightmost bit —


bitset <8> bits("00001010");

cout << bits[0] << endl;   // 0
cout << bits[1] << endl;   // 1

// we can also write to it
bits[0] = 1;

test() method

test(pos) returns the value of the bit at a position — same idea as [ ], but with one important difference —


bitset <8> bits("00001010");

cout << bits.test(1) << endl;   // 1
cout << bits.test(2) << endl;   // 0

💡 test() vs [ ] — The difference is bounds checking. test(pos) checks whether pos is in range and throws an out_of_range exception if it is not. The [ ] operator does no bounds checking — going out of range is undefined behavior. So [ ] is faster, but test() is safer. This is the same relationship vector has between [ ] and at().

Inspecting the bitset

count() method

count() returns how many bits are set to 1 —


bitset <8> bits("10110100");

cout << bits.count() << endl;   // 4

size() method

size() returns the total number of bits in the bitset — which is just the number we declared it with —


bitset <8> bits;

cout << bits.size() << endl;   // 8

any() method

any() returns true if at least one bit is set to 1 —


bitset <8> bits("00000100");

if (bits.any())
{
    cout << "At least one bit is set" << endl;
}

none() method

none() returns true if no bit is set — the opposite of any() —


bitset <8> bits;   // all zeros

if (bits.none())
{
    cout << "No bit is set" << endl;
}

all() method

all() returns true if every bit is set to 1 —


bitset <8> bits("11111111");

if (bits.all())
{
    cout << "Every bit is set" << endl;
}

Converting the bitset

to_string() method

to_string() returns the bitset as a string of ‘0’s and ‘1’s —


bitset <8> bits(42);

string s = bits.to_string();
cout << s << endl;   // 00101010

to_ulong() method

to_ulong() converts the bitset back to an unsigned long —


bitset <8> bits("00101010");

unsigned long value = bits.to_ulong();
cout << value << endl;   // 42

to_ullong() method

For larger bitsets, to_ullong() converts to an unsigned long long —


bitset <64> bits("1111");

unsigned long long value = bits.to_ullong();
cout << value << endl;   // 15

💡 Note on conversion overflow — to_ulong() and to_ullong() throw an overflow_error if the bitset holds a value too big to fit in the target type. So a 100-bit bitset with high bits set cannot be squeezed into an unsigned long long.

Bitwise operators

This is where bitset really shines. Two bitsets of the same size support all the familiar bitwise operators, applied bit by bit.

AND, OR, XOR


bitset <4> a("1100");
bitset <4> b("1010");

cout << (a & b) << endl;   // 1000  (AND)
cout << (a | b) << endl;   // 1110  (OR)
cout << (a ^ b) << endl;   // 0110  (XOR)

NOT

The ~ operator flips every bit, just like flip() —


bitset <4> a("1100");

cout << (~a) << endl;   // 0011

Shift operators

The << and >> operators shift all bits left or right by a given number of positions —


bitset <8> bits("00001111");

cout << (bits << 2) << endl;   // 00111100
cout << (bits >> 2) << endl;   // 00000011

💡 Note on same-size requirement — The binary operators (&, |, ^) only work between two bitsets of the exact same size. A bitset<8> and a bitset<16> cannot be combined directly — the compiler will reject it. This is checked at compile time, which is one of bitset’s quiet strengths.

Printing a bitset

A bitset can be printed straight to cout — it prints as a string of bits, highest position first (left to right) —


bitset <8> bits(42);

cout << bits << endl;   // 00101010

Bitset vs vector<bool> vs set

A common question is when to reach for bitset instead of the alternatives. Here they are side by side.

 

Property bitset vector<bool> set<int>
Size Fixed at compile time Dynamic Dynamic
Memory per bit 1 bit 1 bit (packed) Much higher (tree node)
Bitwise operators (&, |, ^, ~) Yes No No
Built-in count() / any() / all() Yes No No
Iterators / STL algorithms No Yes Yes
Access by position O(1) O(1) O(log n)
C++ version C++98 C++98 C++98
Use when Fixed number of flags, fast bit math A growable array of bits Sparse set of large or unbounded values

 

Time Complexity

 

Operation Description Time Complexity
[ ] operator Access a bit (no bounds check) O(1)
test() Access a bit (with bounds check) O(1)
set(pos) Set a single bit to 1 O(1)
reset(pos) Clear a single bit to 0 O(1)
flip(pos) Toggle a single bit O(1)
set() / reset() / flip() Apply to all bits O(N)
count() Number of bits set to 1 O(N)
any() / all() / none() Check the state of the bits O(N)
size() Total number of bits O(1)
& | ^ ~ (bitwise) Bitwise operations between bitsets O(N)
<< >> (shift) Shift all bits left or right O(N)
to_string() Convert to a string of bits O(N)
to_ulong() / to_ullong() Convert to an integer O(N)

 

Here, N is the number of bits in the bitset. Note that the O(N) operations are very fast in practice, because bitset processes bits a whole machine word (32 or 64 bits) at a time rather than one at a time.

Applications

        • Storing a fixed set of yes/no flags or options compactly (permissions, feature toggles, state flags)
        • The Sieve of Eratosthenes and other “is this number marked?” problems where the range is known
        • Subset and bitmask problems in competitive programming, where each bit represents an item being in or out
        • Fast set membership over a fixed range of integers using AND / OR / XOR between bitsets
        • Speeding up dynamic programming where states can be packed into bits and shifted in bulk
        • Counting set bits (population count) quickly with count()
        • Converting between integers and their binary representation for display or debugging with to_string()
        • Memory-tight environments where an array of bools would waste 8x the space

Putting it all together — a real problem

All these methods are nice on their own, but let us see them working together on an actual problem. A classic one that bitset is perfect for is the Sieve of Eratosthenes — finding all prime numbers up to some limit N.

The idea is simple. We start by assuming every number is prime. Then we walk from 2 upwards, and for each prime we find, we cross out all of its multiples (they cannot be prime). Whatever is left standing at the end is prime.

This is a textbook fit for bitset — we have a fixed range (0 to N) and we only need one bit per number (“is this prime or not?”). Using a bitset instead of an array of bools keeps the memory tiny and the crossing-out fast.

Let us find all primes up to 50 —


#include <iostream>
#include <bitset>
using namespace std;

int main()
{
    const int N = 50;

    // one bit per number from 0 to N
    bitset <N + 1> isPrime;

    // step 1: assume every number is prime
    // set() turns all bits to 1
    isPrime.set();

    // step 2: 0 and 1 are not prime, so reset them
    isPrime.reset(0);
    isPrime.reset(1);

    // step 3: cross out the multiples
    for (int i = 2; i * i <= N; i++)
    {
        // test(i) checks if i is still marked prime
        if (isPrime.test(i))
        {
            // reset every multiple of i, starting from i*i
            for (int j = i * i; j <= N; j += i)
            {
                isPrime.reset(j);
            }
        }
    }

    // step 4: whatever bit is still 1 is a prime
    cout << "Primes up to " << N << ": ";
    for (int i = 2; i <= N; i++)
    {
        if (isPrime.test(i))
        {
            cout << i << " ";
        }
    }
    cout << endl;

    // count() tells us how many primes we found, for free
    cout << "Total primes found: " << isPrime.count() << endl;

    return 0;
}

Output will be —


Primes up to 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Total primes found: 15

Look at how naturally the bitset methods map onto the steps of the algorithm —

        • set() — mark every number as prime to begin with, in one call
        • reset(pos) — cross out a number (0, 1, and every multiple)
        • test(pos) — check whether a number is still marked prime
        • count() — get the total number of primes at the end, with no extra loop

That last point is the kind of small win bitset gives us — we never wrote a counter variable, because count() already knows how many bits are set. This is exactly the situation bitset was built for — a fixed range, one bit of information per slot, and fast bulk operations.

💡 One thing to watch — Because the bitset size must be a compile-time constant, N here is a const int (or it could be a constexpr / #define). If our limit is only known at run time, bitset will not work and we should reach for vector<bool> instead, which can be sized dynamically.

In the next tutorial we will talk about another useful STL container.

Until then
Happy Coding 💻 🎵

Leave a Comment

Your email address will not be published. Required fields are marked *