bitset

Introduction

std::bitset is a fixed-size container in the standard library that stores 0/1 values. Strictly speaking, it is not part of the STL.

bitset and STL

The C++ standard library provides some special container classes, the so-called container adapters (stack, queue, priority queue). In addition, a few classes provide a container-like interface (for example, strings, bitsets, and valarrays). All these classes are covered separately.1 Container adapters and bitsets are covered in Chapter 12.

The C++ standard library provides not only the containers for the STL framework but also some containers that fit some special needs and provide simple, almost self-explanatory, interfaces. You can group these containers into either the so-called container adapters, which adapt standard STL containers to fit special needs, or a bitset, which is a containers for bits or Boolean values. There are three standard container adapters: stacks, queues, and priority queues. In priority queues, the elements are sorted automatically according to a sorting criterion. Thus, the "next" element of a priority queue is the element with the "highest" value. A bitset is a bitfield with an arbitrary but fixed number of bits. Note that the C++ standard library also provides a special container with a variable size for Boolean values: vector.

— Excerpt from The C++ Standard Library 2^nd Edition

Thus, bitset is not part of the STL but is a "Special Container" in the standard library. In fact, as a container, it does not meet the requirements of STL containers. Calling it an adapter is also inaccurate, as it does not rely on other STL containers for its underlying implementation.

Since memory addresses are byte-addressable rather than bit-addressable, a bool variable, although it can only represent 0/1, occupies 1 byte of memory.

bitset optimizes storage by packing eight bits into a single byte, allowing each bit to store a 0/1 value.

For a 4-byte int variable, when storing only 0/1 values, bitset uses only \(\frac{1}{32}\) of its space. When computing certain information, the time required is also \(\frac{1}{32}\) of the original.

In some cases, bitset can optimize program efficiency. Whether it optimizes complexity or constants depends on the perspective. Generally, the complexity of bitset can be expressed in the following ways (assuming the original complexity is \(O(n)\)):

1. \(O(n)\), which considers that bitset does not optimize complexity at all.
2. \(O(\frac n{32})\), which is not rigorous (constants should not appear in complexity) but reflects that bitset can reduce the required time to \(\frac{1}{32}\).
3. \(O(\frac n w)\), where \(w=32\) (the word size of the computer). This notation is widely accepted.
4. \(O(\frac n {\log w})\), where \(w\) is the size of an integer variable on the computer.

Additionally, a specialization of vector, vector<bool>, stores data in the same way as bitset. The difference is that vector<bool> supports dynamic resizing, while bitset is statically allocated at compile time, similar to a regular static array. However, bitset provides useful library functions that are not only convenient but can also enable SIMD optimizations to reduce constants. Moreover, vector<bool> behaves inconsistently with vector in some aspects (e.g., for std::vector<bool> vec, &vec[0] + i is not equal to &vec[i]). Therefore, vector<bool> is generally not used.

Usage

Refer to std::bitset - cppreference.com.

Header File

#include <bitset>

Specifying Size

std::bitset<1000> bs;  // a bitset with 1000 bits

Constructors

• bitset(): All bits are false.
• bitset(unsigned long val): Set to the binary representation of val.
• bitset(const string& str): Set to the binary string str.

Operators

• operator []: Access a specific bit.

• operator ==/operator !=: Compare whether two bitsets are identical.

• operator &/operator &=/operator |/operator |=/operator ^/operator ^=/operator ~: Perform bitwise AND/OR/XOR/NOT operations.

  Note: bitset can only perform bitwise operations with another bitset. To perform bitwise operations with an integer, the integer must first be converted to a bitset.

• operator <</operator >>/operator <<=/operator >>=: Perform binary left/right shifts.

Additionally, bitset supports C++ stream I/O, meaning you can input/output via cin/cout.

Member Functions

• count(): Returns the number of true bits.
• size(): Returns the size of the bitset.
• test(pos): Similar to at() in vector, performs bounds checking, unlike [].
• any(): Returns true if any bit is true, otherwise false.
• none(): Returns true if all bits are false, otherwise false.
• all(): Returns true if all bits are true, otherwise false.
• 1. set(): Sets all bits to true.
  2. set(pos, val = true): Sets a specific bit to true/false.
• 1. reset(): Sets all bits to false.
  2. reset(pos): Sets a specific bit to false. Equivalent to set(pos, false).
• 1. flip(): Flips all bits (\(0\leftrightarrow1\), equivalent to XOR with an all-ones bitset).
  2. flip(pos): Flips a specific bit.
• to_string(): Returns a string representation.
• to_ulong(): Returns an unsigned long representation (long is the same as int on NT and 32-bit POSIX systems, and the same as long long on 64-bit POSIX).
• to_ullong(): (Since C++11) Returns an unsigned long long representation.

Additionally, libstdc++ provides some practical internal member functions¹:

• _Find_first(): Returns the index of the first true bit, or the size of the bitset if no true bit exists.
• _Find_next(pos): Returns the index of the first true bit after pos (strictly greater than pos), or the size of the bitset if no such bit exists.

Applications

「LibreOJ β Round #2」Greedy Can Only Pass Sample Cases

This problem can be solved with DP. The transition is simple:

Let \(f(i,j)\) denote whether the sum of squares of the first \(i\) numbers can be \(j\). Then \(f(i,j)=\bigvee\limits_{k=a}^bf(i-1,j-k^2)\) (logical OR).

However, a naive implementation would be \(O(n^5)\), which seems too slow.

We can optimize using bitset by shifting left and ORing:

Submission Record: std::bitset

#include <bitset>
#include <cstdio>
#include <iostream>

using namespace std;

constexpr int N = 101;

int n, a[N], b[N];
bitset<N * N * N> f[N];

int main() {
  int i, j;

  cin >> n;

  for (i = 1; i <= n; ++i) cin >> a[i] >> b[i];

  f[0][0] = 1;

  for (i = 1; i <= n; ++i) {
    for (j = a[i]; j <= b[i]; ++j) {
      f[i] |= (f[i - 1] << (j * j));
    }
  }

  cout << f[n].count();

  return 0;
}

Since libstdc++'s implementation packs __CHAR_BIT__ * sizeof(unsigned long) bits², which is \(32\) on some platforms, we can manually implement bitset (only needing to support left shift and OR) packing \(64\) bits (__CHAR_BIT__ * sizeof(unsigned long long)) for further optimization:

Submission Record: Handwritten bitset

#include <cstdio>
#include <iostream>

using namespace std;

constexpr int N = 101;
constexpr int W = 64;

struct Bitset {
  unsigned long long a[N * N * N >> 6];

  void shiftor(const Bitset &y, int p, int l, int r) {
    int t = p - p / W * W;
    int tt = (t == 0 ? 0 : W - t);
    int to = (r + p) / W;
    int qaq = (p + W - 1) / W;

    for (int i = (l + p) / W; i <= to; ++i) {
      if (i - qaq >= 0) a[i] |= y.a[i - qaq] >> tt;

      a[i] |= ((y.a[i - qaq + 1] & ((1ull << tt) - 1)) << t);
    }
  }
} f[N];

int main() {
  int n, a, b, l = 0, r = 0, ans = 0;

  scanf("%d", &n);

  f[0].a[0] = 1;

  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &a, &b);

    for (int j = a; j <= b; ++j) f[i].shiftor(f[i - 1], j * j, l, r);

    l += a * a;
    r += b * b;
  }

  for (int i = l / W; i <= r / W; ++i)
    ans += __builtin_popcount(f[n].a[i] & 0xffffffffu) +
           __builtin_popcount(f[n].a[i] >> 32);

  printf("%d", ans);

  return 0;
}

Additionally, a brute-force approach with some pruning can also pass:

Submission Record: Brute-force with pruning

#include <cstdio>
#include <iostream>

using namespace std;

constexpr int N = 101;
constexpr int W = 64;

bool f[N * N * N];

int main() {
  int n, i, j, k, a, b, l = 0, r = 0, ans = 0;

  scanf("%d", &n);

  f[0] = true;

  for (i = 1; i <= n; ++i) {
    scanf("%d%d", &a, &b);
    l += a * a;
    r += b * b;

    for (j = r; j >= l; --j) {
      f[j] = false;

      for (k = a; k <= b; ++k) {
        if (j - k * k < l - a * a) break;

        if (f[j - k * k]) {
          f[j] = true;
          break;
        }
      }
    }
  }

  for (i = l; i <= r; ++i) ans += f[i];

  printf("%d", ans);

  return 0;
}

CF1097F Alex and a TV Show

Problem

You are given \(n\) multisets and four types of operations:

1. Set a multiset to a single number.
2. Set a multiset to the sum of two other multisets.
3. Set a multiset to the set of \(\gcd\) of pairs from two other multisets. That is: \(A=\{\gcd(x,y)|x\in B,y\in C\}\).
4. Query the count of a number in a multiset, modulo 2.

Number of multisets: \(10^5\), number of operations: \(10^6\), value range: \(7000\).

Solution

Seeing "modulo 2", we can think of using bitset to maintain each multiset.

Thus, operation 1 is direct assignment, operation 2 is XOR (since modulo 2), operation 4 is direct lookup, but .. what about operation 3?

We can try to maintain the multiset of all divisors of each multiset. Then operation 3 becomes a direct bitwise AND.

We can precompute the bitset of divisors for each number in the value range, solving operation 1. Operation 2 remains XOR.

Now the problem is: given the multiset of divisors of a multiset, how to get the count of a specific number in the original multiset.

Let the original multiset be \(A\), and its divisor multiset be \(A'\). We want the count of \(x\) in \(A\). Using Möbius inversion:

\[ \begin{aligned}&\sum\limits_{i\in A}[\frac i x=1]\\=&\sum\limits_{i\in A}\sum\limits_{d|\frac i x}\mu(d)\\=&\sum\limits_{d\in A',x|d}\mu(\frac d x)\end{aligned} \]

Since we are working modulo \(2\), \(-1\) and \(1\) are the same; we only need to check whether \(\frac d x\) has any square factors. Thus, we can precompute for each number in the value range a bitset of positions among its multiples that, when divided by it, are square-free. When answering queries, we bitwise AND and then count().

The complexity per query is \(O(\frac v w)\) (\(v=7000,\,w=32\)).

As for preprocessing, \(O(v\sqrt v)\) or \(O(v^2)\) preprocessing is straightforward. Logarithmic preprocessing is shown in the code below, with complexity being the harmonic series, i.e., \(O(v\log v)\).

Reference Code

#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

int read() {
  int out = 0;
  char c;
  while (!isdigit(c = getchar()));
  for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
  return out;
}

constexpr int N = 100005;
constexpr int M = 1000005;
constexpr int V = 7005;

bitset<V> pre[V], pre2[V], a[N], mu;
int n, m, tot;
char ans[M];

int main() {
  int i, j, x, y, z;

  n = read();
  m = read();

  mu.set();
  for (i = 2; i * i < V; ++i) {
    for (j = 1; i * i * j < V; ++j) {
      mu[i * i * j] = 0;
    }
  }
  for (i = 1; i < V; ++i) {
    for (j = 1; i * j < V; ++j) {
      pre[i * j][i] = 1;
      pre2[i][i * j] = mu[j];
    }
  }

  while (m--) {
    switch (read()) {
      case 1:
        x = read();
        y = read();
        a[x] = pre[y];
        break;
      case 2:
        x = read();
        y = read();
        z = read();
        a[x] = a[y] ^ a[z];
        break;
      case 3:
        x = read();
        y = read();
        z = read();
        a[x] = a[y] & a[z];
        break;
      case 4:
        x = read();
        y = read();
        ans[tot++] = ((a[x] & pre2[y]).count() & 1) + '0';
        break;
    }
  }

  printf("%s", ans);

  return 0;
}

Combined with the Sieve of Eratosthenes

Due to bitset's fast sequential read/write efficiency, it is well-suited for generating prime tables when combined with the Sieve of Eratosthenes.

The method is simple: just replace the boolean array in the Sieve of Eratosthenes with a bitset.

Speed Test

Using Quick C++ Benchmarks for testing, compiler: GCC 13.2, compile flags: -std=c++20 -O2.

Algorithm	Function Name
Sieve of Eratosthenes + C-style bool array, no prime storage	Eratosthenes_CArray
Sieve of Eratosthenes + vector<bool>, no prime storage	Eratosthenes_vector
Sieve of Eratosthenes + bitset, no prime storage	Eratosthenes_bitset
Sieve of Eratosthenes + C-style bool array, with prime storage	Eratosthenes_CArray_sp
Sieve of Eratosthenes + vector<bool>, with prime storage	Eratosthenes_vector_sp
Sieve of Eratosthenes + bitset, with prime storage	Eratosthenes_bitset_sp
Euler's Sieve + C-style bool array	Euler_CArray
Euler's Sieve + vector<bool>	Euler_vector
Euler's Sieve + bitset	Euler_bitset

• When the Sieve of Eratosthenes stores the primes:

  • Test result for \(N=5 \times 10^7 + 1\):

    

  • Test result for \(N=10^8 + 1\):

    

• When the Sieve of Eratosthenes does not store the primes:

  • Test result for \(N=5 \times 10^7 + 1\):

    

  • Test result for \(N=10^8 + 1\):

    

From the test results:

1. The Sieve of Eratosthenes with complexity \(O(n \log \log n)\), when optimized with bitset or vector<bool>, can outperform Euler's Sieve with complexity \(O(n)\);
2. Euler's Sieve shows insignificant optimization with bitset or vector<bool> in most cases;
3. bitset optimization is slightly stronger than vector<bool>.

Reference Code

Requires google/benchmark installed.

#include <benchmark/benchmark.h>
#include <bits/stdc++.h>
using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;

#define ERATOSTHENES_STORAGE_PRIME
#define ENABLE_EULER
constexpr u32 N = 5e7 + 1;

#ifndef ERATOSTHENES_STORAGE_PRIME

void Eratosthenes_CArray(benchmark::State &state) {
  static bool is_prime[N];
  for (auto _ : state) {
    fill(is_prime, is_prime + N, true);
    is_prime[0] = is_prime[1] = false;
    for (u32 i = 2; (u64)i * i < N; ++i)
      if (is_prime[i])
        for (u32 j = i * i; j < N; j += i) is_prime[j] = false;
    benchmark::DoNotOptimize(0);
  }
}

BENCHMARK(Eratosthenes_CArray);

void Eratosthenes_vector(benchmark::State &state) {
  static vector<bool> is_prime(N);
  for (auto _ : state) {
    fill(is_prime.begin(), is_prime.end(), true);
    is_prime[0] = is_prime[1] = false;
    for (u32 i = 2; (u64)i * i < N; ++i)
      if (is_prime[i])
        for (u32 j = i * i; j < N; j += i) is_prime[j] = false;
    benchmark::DoNotOptimize(0);
  }
}

BENCHMARK(Eratosthenes_vector);

void Eratosthenes_bitset(benchmark::State &state) {
  static bitset<N> is_prime;
  for (auto _ : state) {
    is_prime.set();
    is_prime.reset(0);
    is_prime.reset(1);
    for (u32 i = 2; (u64)i * i < N; ++i)
      if (is_prime[i])
        for (u32 j = i * i; j < N; j += i) is_prime.reset(j);
    benchmark::DoNotOptimize(0);
  }
}

BENCHMARK(Eratosthenes_bitset);

#else

void Eratosthenes_CArray_sp(benchmark::State &state) {
  static bool is_prime[N];
  for (auto _ : state) {
    vector<u32> prime;
    fill(is_prime, is_prime + N, true);
    is_prime[0] = is_prime[1] = false;
    for (u32 i = 2; (u64)i * i < N; ++i)
      if (is_prime[i])
        for (u32 j = i * i; j < N; j += i) is_prime[j] = false;
    for (u32 i = 2; i < N; ++i)
      if (is_prime[i]) prime.push_back(i);
    benchmark::DoNotOptimize(prime);
  }
}

BENCHMARK(Eratosthenes_CArray_sp);

void Eratosthenes_vector_sp(benchmark::State &state) {
  static vector<bool> is_prime(N);
  for (auto _ : state) {
    vector<u32> prime;
    fill(is_prime.begin(), is_prime.end(), true);
    is_prime[0] = is_prime[1] = false;
    for (u32 i = 2; (u64)i * i < N; ++i)
      if (is_prime[i])
        for (u32 j = i * i; j < N; j += i) is_prime[j] = false;
    for (u32 i = 2; i < N; ++i)
      if (is_prime[i]) prime.push_back(i);
    benchmark::DoNotOptimize(prime);
  }
}

BENCHMARK(Eratosthenes_vector_sp);

void Eratosthenes_bitset_sp(benchmark::State &state) {
  static bitset<N> is_prime;
  for (auto _ : state) {
    vector<u32> prime;
    is_prime.set();
    is_prime.reset(0);
    is_prime.reset(1);
    for (u32 i = 2; (u64)i * i < N; ++i)
      if (is_prime[i])
        for (u32 j = i * i; j < N; j += i) is_prime.reset(j);
    for (u32 i = 2; i < N; ++i)
      if (is_prime[i]) prime.push_back(i);
    benchmark::DoNotOptimize(prime);
  }
}

BENCHMARK(Eratosthenes_bitset_sp);

#endif

#ifdef ENABLE_EULER

void Euler_CArray(benchmark::State &state) {
  static bool not_prime[N];
  for (auto _ : state) {
    vector<u32> prime;
    fill(not_prime, not_prime + N, false);
    not_prime[0] = not_prime[1] = true;
    for (u32 i = 2; i < N; ++i) {
      if (!not_prime[i]) prime.push_back(i);
      for (u32 pri_j : prime) {
        if (i * pri_j >= N) break;
        not_prime[i * pri_j] = true;
        if (i % pri_j == 0) break;
      }
    }
    benchmark::DoNotOptimize(prime);
  }
}

BENCHMARK(Euler_CArray);

void Euler_vector(benchmark::State &state) {
  static vector<bool> not_prime(N);
  for (auto _ : state) {
    vector<u32> prime;
    fill(not_prime.begin(), not_prime.end(), false);
    not_prime[0] = not_prime[1] = true;
    for (u32 i = 2; i < N; ++i) {
      if (!not_prime[i]) prime.push_back(i);
      for (u32 pri_j : prime) {
        if (i * pri_j >= N) break;
        not_prime[i * pri_j] = true;
        if (i % pri_j == 0) break;
      }
    }
    benchmark::DoNotOptimize(prime);
  }
}

BENCHMARK(Euler_vector);

void Euler_bitset(benchmark::State &state) {
  static bitset<N> not_prime;
  for (auto _ : state) {
    vector<u32> prime;
    not_prime.reset();
    not_prime.set(0);
    not_prime.set(1);
    for (u32 i = 2; i < N; ++i) {
      if (!not_prime[i]) prime.push_back(i);
      for (u32 pri_j : prime) {
        if (i * pri_j >= N) break;
        not_prime.set(i * pri_j);
        if (i % pri_j == 0) break;
      }
    }
    benchmark::DoNotOptimize(prime);
  }
}

BENCHMARK(Euler_bitset);

#endif

static void Noop(benchmark::State &state) {
  for (auto _ : state) benchmark::DoNotOptimize(0);
}

BENCHMARK(Noop);
BENCHMARK_MAIN();

Combined with Tree Decomposition

bitset combined with tree decomposition can solve a class of problems involving queries on multiple tree paths. See Data Structures/Tree Decomposition.

Combined with Mo's Algorithm

See Miscellaneous/Mo's Algorithm with bitset.

Computing High-Dimensional Partial Orders

See FHR Slides.

References and Notes

---

1. libstdc++: SGI STL extensions ↩

2. libstdc++: std::bitset<_Nb> Class Template Reference ↩

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用