AIOJ

Introduction

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

bitset and the 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.

——Quoted from The C++ Standard Library 2nd Edition

This shows that bitset is not part of the STL, but is a "Special Container" in the standard library. In fact, as a container, it does not satisfy the requirements for STL containers. Calling it an adapter would also be inaccurate, since it does not use another STL container as its underlying implementation.

Because memory addresses are byte-addressed, rather than bit-addressed, a variable of type bool, although it can represent only 0/1, still occupies 1 byte of memory.

bitset uses fixed optimization so that the eight bits in one byte can separately store 8 bits of 0/1.

For a 4-byte int variable, when storing only 0/1 values, a bitset uses only $\frac{1}{32}$ of the space, and the time required to compute some information is also $\frac 1{32}$ of that for the int.

In some cases, bitset can improve program runtime. Whether it optimizes the complexity or only the constant depends on how computational complexity is viewed. In general, the complexity of bitset can be written in several ways (assuming the original complexity is $O(n)$ ):

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

In addition, the storage method of the vector specialization vector<bool> is the same as that of bitset. The difference is that it supports dynamically allocating space, while bitset, like an ordinary static array, is allocated at compile time. However, bitset has some useful library functions that are not only convenient but can sometimes enable SIMD and thus reduce constants. In addition, some behavior of vector<bool> differs from that of vector (for example, for std::vector<bool> vec, &vec[0] + i is not equal to &vec[i]). Therefore, vector<bool> is generally not used.

Usage

See std::bitset - cppreference.com.

Header

#include <bitset>

Specifying the size

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

Constructors

bitset(): Every bit is false.
bitset(unsigned long val): Set to the binary form of val.
bitset(const string& str): Set to the $01$ string str.

Operators

operator []: Access a specific bit.
operator ==/operator !=: Compare whether the contents of two bitsets are exactly the same.
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 type, first convert the integer to a bitset.
operator <</operator >>/operator <<=/operator >>=: Perform binary left/right shifts.

In addition, bitset supports C++ stream I/O, which means that input and output can be performed through cin/cout.

Member functions

count(): Return the number of true bits.
size(): Return the size of the bitset.
test(pos): Has the same function as vector's at(); unlike the [] operator, it performs bounds checking.
any(): Return true if any bit is true, and false otherwise.
none(): If all bits are false, return true; otherwise return false.
all(): Return true if all bits are true, and false otherwise.
1. set(): Set the entire bitset to true.
2. set(pos, val = true): Set one bit to true/false.
1. reset(): Set the entire bitset to false.
2. reset(pos): Set one bit to false. Equivalent to set(pos, false).
1. flip(): Flip every bit. ( $0\leftrightarrow1$ , equivalent to XORing with an all- $1$ bitset.)
2. flip(pos): Flip one bit.
to_string(): Return the converted string representation.
to_ulong(): Return the converted 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 systems).
to_ullong(): (Since C++11) Return the converted unsigned long long representation.

In addition, libstdc++ has several useful internal member functions¹:

_Find_first(): For the bitset, return the index of its first true; if there is no true, return the size of the bitset.
_Find_next(pos): For pos, after it (at an index strictly greater than pos), return the index of the first true; if after pos there is no true, return the size of the bitset.

Applications

LibreOJ β Round #2: Greedy Only Passes the Sample

This problem can be solved with DP, and the transition equation is very simple:

$f(i,j)$ indicates whether the sum of the squares of the first $i$ numbers can be $j$ , so $f(i,j)=\bigvee\limits_{k=a}^bf(i-1,j-k^2)$ (ORed together).

However, a direct solution takes $O(n^5)$ time and seemingly cannot pass.

We can optimize it with bitset: just shift left and OR.

Submission: 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 the libstdc++ implementation packs __CHAR_BIT__ * sizeof(unsigned long) bits², which is $32$ on some platforms, we can hand-write a bitset (only needing to support shifting left and ORing) that packs $64$ bits (__CHAR_BIT__ * sizeof(unsigned long long)) for further optimization:

Submission: hand-written 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;
}

In addition, a brute-force solution with several pruning techniques can also pass:

Submission: brute force with several pruning techniques

#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 statement

You are given $n$ multisets and four types of operations:

Set a multiset to a number.
Set a multiset to the sum of two other multisets.
Set a multiset to the $\gcd$ of one number selected from each of two other multisets. That is, $A=\{\gcd(x,y)|x\in B,y\in C\}$ .
Query the number of occurrences of a number in a multiset, modulo 2.

The number of multisets is $10^5$ , the number of operations is $10^6$ , and the value range is $7000$ .

Solution

Seeing ‘modulo $2$ ’ suggests maintaining each multiset with a bitset.

Then operation $1$ is a direct assignment, operation $2$ is XOR (because of modulo $2$ ), and operation $4$ is a direct query. But what about operation $3$ ?

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

We can precompute the bitset of divisors for every number in the value range, which solves operation $1$ . Operation $2$ is still XOR.

The problem now is how to obtain the number of occurrences of a number in a multiset from the multiset of its divisors.

Let the original multiset be $A$ , and let the multiset of its divisors be $A'$ . We want the number of occurrences in $A$ of $x$ . Applying Möbius inversion, we get:

\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}

Because this is modulo $2$ , $-1$ and $1$ are the same, so we only need to check whether $\frac d x$ has a square factor. Therefore, for every number in the value range, we can precompute a bitset consisting of the multiples of that number whose quotient after division by it is square-free. When obtaining the answer, simply take the bitwise AND first and then call count().

Then the complexity of a single query is $O(\frac v w)$ ( $v=7000,\,w=32$ ).

For preprocessing, $O(v\sqrt v)$ or $O(v^2)$ preprocessing is relatively simple. The $\log$ preprocessing shown in the code below has harmonic-series complexity, so it is $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;
}

Combining with the sieve of Eratosthenes

Because of its fast sequential read and write performance, bitset is particularly suitable for combining with the sieve of Eratosthenes to build a table of primes.

The method is also simple: just replace the Boolean array in the sieve of Eratosthenes with a bitset.

Benchmark

The benchmark uses Quick C++ Benchmarks, with GCC 13.2 as the compiler and -std=c++20 -O2 as compilation parameters.

Algorithm	Function name
Sieve of Eratosthenes + C-style Boolean array, without storing the sieved primes	`Eratosthenes_CArray`
Sieve of Eratosthenes + `vector<bool>`, without storing the sieved primes	`Eratosthenes_vector`
Sieve of Eratosthenes + `bitset`, without storing the sieved primes	`Eratosthenes_bitset`
Sieve of Eratosthenes + C-style Boolean array, storing the sieved primes	`Eratosthenes_CArray_sp`
Sieve of Eratosthenes + `vector<bool>`, storing the sieved primes	`Eratosthenes_vector_sp`
Sieve of Eratosthenes + `bitset`, storing the sieved primes	`Eratosthenes_bitset_sp`
Euler sieve + C-style Boolean array	`Euler_CArray`
Euler sieve + `vector<bool>`	`Euler_vector`
Euler sieve + `bitset`	`Euler_bitset`

When the sieve of Eratosthenes stores the sieved primes:
- For $N=5 \times 10^7 + 1$ , benchmark results:
- For $N=10^8 + 1$ , benchmark results:
When the sieve of Eratosthenes does not store the sieved primes:
- For $N=5 \times 10^7 + 1$ , benchmark results:
- For $N=10^8 + 1$ , benchmark results:

The benchmark results show:

After optimization with bitset or vector<bool>, the sieve of Eratosthenes with time complexity $O(n \log \log n)$ can even outperform the Euler sieve with time complexity $O(n)$ ;
In most cases, the optimization effect of using bitset or vector<bool> with the Euler sieve is not obvious;
The optimization effect of bitset is slightly stronger than that of vector<bool>.

Reference code

Install google/benchmark first.

#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();

Combining with tree decomposition

Combining bitset with tree decomposition can solve a class of problems that ask for the sum of information on multiple paths in a tree. See Data Structures/Tree Decomposition for details.

bitset