Introduction

std::bitset is compact and fast for fixed-size bit flags, but iterating only the set bits can be tricky. A naive scan over all positions is simple and sometimes acceptable, yet sparse bitsets benefit from bit-twiddling approaches. This guide compares practical strategies and shows when each one is worth using.

Baseline: Scan Every Position

The simplest method is checking each index with test or operator[]. Complexity is linear in bitset size, independent of how many bits are set.

1#include <bitset>
2#include <iostream>
3
4int main() {
5    std::bitset<16> bs(std::string("1010010000001001"));
6
7    for (std::size_t i = 0; i < bs.size(); ++i) {
8        if (bs.test(i)) {
9            std::cout << "set bit at index " << i << "\n";
10        }
11    }
12}

This is often good enough for small N or dense bitsets. It is also the easiest to maintain.

Faster Iteration for Small Fixed Width

If the bitset fits into an unsigned integer, you can extract that value and iterate set bits using x & -x style operations. This walks only set bits.

1#include <bitset>
2#include <cstdint>
3#include <iostream>
4
5int main() {
6    std::bitset<64> bs;
7    bs.set(1);
8    bs.set(7);
9    bs.set(40);
10
11    std::uint64_t x = bs.to_ullong();
12
13    while (x != 0) {
14        std::uint64_t lsb = x & (~x + 1); // isolate lowest set bit
15        unsigned idx = __builtin_ctzll(x); // GCC and Clang
16        std::cout << "set bit at index " << idx << "\n";
17        x ^= lsb; // clear isolated bit
18    }
19}

For sparse flags this is much faster because work scales with number of set bits, not total width.

General Approach for Larger std::bitset

std::bitset does not provide find_first and find_next APIs like some other containers. For very large compile-time sizes, a common pattern is storing data in machine-word chunks and iterating each chunk with trailing-zero operations.

If you control data representation, consider using an array of uint64_t for iteration-heavy workloads. You still get compact storage, but iteration logic is naturally set-bit oriented.

1#include <array>
2#include <cstdint>
3#include <iostream>
4
5template <std::size_t Words>
6void iterate_set_bits(const std::array<std::uint64_t, Words>& blocks) {
7    for (std::size_t w = 0; w < Words; ++w) {
8        std::uint64_t x = blocks[w];
9        while (x != 0) {
10            unsigned bit = __builtin_ctzll(x);
11            std::size_t global_index = w * 64 + bit;
12            std::cout << "set bit at index " << global_index << "\n";
13            x &= (x - 1); // clear lowest set bit
14        }
15    }
16}
17
18int main() {
19    std::array<std::uint64_t, 2> blocks{};
20    blocks[0] |= (1ULL << 3);
21    blocks[0] |= (1ULL << 9);
22    blocks[1] |= (1ULL << 1);
23
24    iterate_set_bits(blocks);
25}

This pattern is common in schedulers, bitmap indexes, and simulation engines.

Choosing the Right Technique

Use full scan when:

• bitset size is small
• density is high
• readability matters more than micro-optimization

Use set-bit iteration when:

• bitset is sparse
• iteration is in a hot path
• you can operate in word chunks safely

Profile before rewriting. In many applications the simple scan is fast enough, and complexity cost of specialized bit hacks is not justified.

Portability Notes

Compiler intrinsics such as __builtin_ctzll are widely available on GCC and Clang. On C++20, std::countr_zero from bit header can be a cleaner standard alternative.

1#include <bit>
2#include <cstdint>
3#include <iostream>
4
5int main() {
6    std::uint64_t x = 0b1010000;
7    std::cout << std::countr_zero(x) << "\n";
8}

For cross-platform libraries, wrap intrinsic or standard calls behind a small utility function and centralize fallback behavior.

Common Pitfalls

• Assuming std::bitset has built-in find_next style iteration helpers.
• Using to_ullong on bitsets wider than supported conversion range.
• Forgetting that index ordering in printed bitset strings can be counterintuitive.
• Applying set-bit tricks without checking zero values before trailing-zero calls.
• Optimizing iteration prematurely without profiling actual hot paths.

Summary

• A full index scan is simplest and often sufficient for std::bitset.
• Sparse bitsets benefit from iterating set bits via word-level bit operations.
• For large workloads, chunked integer storage can outperform direct bitset scanning.
• Use portable wrappers for trailing-zero operations across compilers.
• Choose complexity level based on measured bottlenecks, not assumption.