跳转至

bitset

介紹

std::bitset 是標準庫中的一個存儲 0/1 的大小不可變容器。嚴格來講，它並不屬於 STL。

bitset 與 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.

——摘自《The C++ Standard Library 2nd Edition》

由此看來，bitset 並不屬於 STL，而是一種標準庫中的 "Special Container"。事實上，它作為一種容器，也並不滿足 STL 容器的要求。説它是適配器，它也並不依賴於其它 STL 容器作為底層實現。

由於內存地址是按字節即 byte 尋址，而非比特 bit，一個 bool 類型的變量，雖然只能表示 0/1, 但是也佔了 1 byte 的內存。

bitset 就是通過固定的優化，使得一個字節的八個比特能分別儲存 8 位的 0/1。

對於一個 4 字節的 int 變量，在只存 0/1 的意義下，bitset 佔用空間只是其 \(\frac{1}{32}\)，計算一些信息時，所需時間也是其 \(\frac 1{32}\)。

在某些情況下通過 bitset 可以優化程序的運行效率。至於其優化的是複雜度還是常數，要看計算複雜度的角度。一般 bitset 的複雜度有以下幾種記法：（設原複雜度為 \(O(n)\)）

  1. \(O(n)\)，這種記法認為 bitset 完全沒有優化複雜度。
  2. \(O(\frac n{32})\)，這種記法不太嚴謹（複雜度中不應出現常數），但體現了 bitset 能將所需時間優化至 \(\frac 1{32}\)。
  3. \(O(\frac n w)\)，其中 \(w=32\)（計算機的位數），這種記法較為普遍接受。
  4. \(O(\frac n {\log w})\)，其中 \(w\) 為計算機一個整型變量的大小。

另外，vector 的一個特化 vector<bool> 的儲存方式同 bitset 一樣，區別在於其支持動態開空間，bitset 則和我們一般的靜態數組一樣，是在編譯時就開好了的。然而，bitset 有一些好用的庫函數，不僅方便，而且有時可以實現 SIMD 進而減小常數。另外，vector<bool> 的部分表現和 vector 不一致（如對 std::vector<bool> vec 來説，&vec[0] + i 不等於 &vec[i]）。因此，一般不使用 vector<bool>。

使用

參見 std::bitset - cppreference.com。

頭文件

1
#include <bitset>

指定大小

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

構造函數

  • bitset(): 每一位都是 false。
  • bitset(unsigned long val): 設為 val 的二進制形式。
  • bitset(const string& str): 設為 \(01\) 串 str。

運算符

  • operator []: 訪問其特定的一位。

  • operator ==/operator !=: 比較兩個 bitset 內容是否完全一樣。

  • operator &/operator &=/operator |/operator |=/operator ^/operator ^=/operator ~: 進行按位與/或/異或/取反操作。

    注意：bitset 只能與 bitset 進行位運算，若要和整型進行位運算，要先將整型轉換為 bitset。

  • operator <</operator >>/operator <<=/operator >>=: 進行二進制左移/右移。

此外，bitset 還提供了 C++ 流式 IO 的支持，這意味着你可以通過 cin/cout 進行輸入輸出。

成員函數

  • count(): 返回 true 的數量。
  • size(): 返回 bitset 的大小。
  • test(pos): 它和 vector 中的 at() 的作用是一樣的，和 [] 運算符的區別就是越界檢查。
  • any(): 若存在某一位是 true 則返回 true，否則返回 false。
  • none(): 若所有位都是 false 則返回 true，否則返回 false。
  • all(): 若所有位都是 true 則返回 true，否則返回 false。
    1. set(): 將整個 bitset 設置成 true。
    2. set(pos, val = true): 將某一位設置成 true/false。
    1. reset(): 將整個 bitset 設置成 false。
    2. reset(pos): 將某一位設置成 false。相當於 set(pos, false)。
    1. flip(): 翻轉每一位。（\(0\leftrightarrow1\)，相當於異或一個全是 \(1\) 的 bitset）
    2. flip(pos): 翻轉某一位。
  • to_string(): 返回轉換成的字符串表達。
  • to_ulong(): 返回轉換成的 unsigned long 表達（long 在 NT 及 32 位 POSIX 系統下與 int 一樣，在 64 位 POSIX 下與 long long 一樣）。
  • to_ullong():（C++11 起）返回轉換成的 unsigned long long 表達。

另外，libstdc++ 中有一些較為實用的內部成員函數1：

  • _Find_first(): 返回 bitset 第一個 true 的下標，若沒有 true 則返回 bitset 的大小。
  • _Find_next(pos): 返回 pos 後面（下標嚴格大於 pos 的位置）第一個 true 的下標，若 pos 後面沒有 true 則返回 bitset 的大小。

應用

「LibreOJ β Round #2」貪心只能過樣例

這題可以用 dp 做，轉移方程很簡單：

\(f(i,j)\) 表示前 \(i\) 個數的平方和能否為 \(j\)，那麼 \(f(i,j)=\bigvee\limits_{k=a}^bf(i-1,j-k^2)\)（或起來）。

但如果直接做的話是 \(O(n^5)\) 的，（看起來）過不了。

發現可以用 bitset 優化，左移再或起來就好了：

提交記錄：std::bitset 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bitset>
#include <cstdio>
#include <iostream>

using namespace std;

const 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;
}

由於 libstdc++ 的實現為壓 __CHAR_BIT__ * sizeof(unsigned long) 位的2，在一些平台中其為 \(32\)。所以，可以手寫 bitset（只需要支持左移後或起來這一種操作）壓 \(64\) 位（__CHAR_BIT__ * sizeof(unsigned long long)）來進一步優化：

提交記錄：手寫 bitset 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 101;
const 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 (register 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 (register int i = 1; i <= n; ++i) {
    scanf("%d%d", &a, &b);

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

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

  for (register 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;
}

另外，加了幾個剪枝的暴力也能過：

提交記錄：加了幾個剪枝的暴力 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 101;
const 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

題意

給你 \(n\) 個可重集，四種操作：

  1. 把某個可重集設為一個數。
  2. 把某個可重集設為另外兩個可重集加起來。
  3. 把某個可重集設為從另外兩個可重集中各選一個數的 \(\gcd\)。即：\(A=\{\gcd(x,y)|x\in B,y\in C\}\)。
  4. 詢問某個可重集中某個數的個數，在模 2 意義下。

可重集個數 \(10^5\)，操作個數 \(10^6\)，值域 \(7000\)。

做法

看到「在模 \(2\) 意義下」，可以想到用 bitset 維護每個可重集。

這樣的話，操作 \(1\) 直接設，操作 \(2\) 就是異或（因為模 \(2\)），操作 \(4\) 就是直接查，但 .. 操作 \(3\) 怎麼辦？

我們可以嘗試維護每個可重集的所有約數構成的可重集，這樣的話，操作 \(3\) 就是直接按位與。

我們可以把值域內每個數的約數構成的 bitset 預處理出來，這樣操作 \(1\) 就解決了。操作 \(2\) 仍然是異或。

現在的問題是，如何通過一個可重集的約數構成的可重集得到該可重集中某個數的個數。

令原可重集為 \(A\)，其約數構成的可重集為 \(A'\)，我們要求 \(A\) 中 \(x\) 的個數，用 莫比烏斯反演 推一推：

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

由於是模 \(2\) 意義下，\(-1\) 和 \(1\) 是一樣的，只用看 \(\frac d x\) 有沒有平方因子即可。所以，可以對值域內每個數預處理出其倍數中除以它不含平方因子的位置構成的 bitset，求答案的時候先按位與再 count() 就好了。

這樣的話，單次詢問複雜度就是 \(O(\frac v w)\)（\(v=7000,\,w=32\)）。

至於預處理的部分，\(O(v\sqrt v)\) 或者 \(O(v^2)\) 預處理比較簡單，\(\log\) 預處理就如下面代碼所示，複雜度為調和級數，所以是 \(O(v\log v)\)。

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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;
}

const int N = 100005;
const int M = 1000005;
const 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;
}

與埃氏篩結合

由於 bitset 快速的連續讀寫效率，使得它非常適合用於與 埃氏篩 結合打質數表。

使用的方式也很簡單，只需要將埃氏篩中的布爾數組替換成 bitset 即可。

速度測試

使用 Quick C++ Benchmarks 進行測試，編譯器採用 GCC 13.2，編譯參數為 -std=c++20 -O2。

算法 函數名
埃氏篩 + C 風格布爾數組，不存儲篩出來的素數 Eratosthenes_CArray
埃氏篩 +vector<bool>，不存儲篩出來的素數 Eratosthenes_vector
埃氏篩 +bitset，不存儲篩出來的素數 Eratosthenes_bitset
埃氏篩 + C 風格布爾數組，存儲篩出來的素數 Eratosthenes_CArray_sp
埃氏篩 +vector<bool>，存儲篩出來的素數 Eratosthenes_vector_sp
埃氏篩 +bitset，存儲篩出來的素數 Eratosthenes_bitset_sp
歐拉篩 + C 風格布爾數組 Euler_CArray
歐拉篩 +vector<bool> Euler_vector
歐拉篩 +bitset Euler_bitset

  • 當埃氏篩 存儲 篩出來的素數時：

  • 當埃氏篩 不存儲 篩出來的素數時：

從測試結果中可知：

  1. 時間複雜度 \(O(n \log \log n)\) 的埃氏篩在使用 bitset 或 vector<bool> 優化後，性能甚至超過時間複雜度 \(O(n)\) 的歐拉篩；
  2. 歐拉篩使用 bitset 或 vector<bool> 後的優化效果在大多數情況下均不明顯；
  3. bitset 的優化效果略強於 vector<bool>。
參考代碼

需安裝 google/benchmark。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#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();

與樹分塊結合

bitset 與樹分塊結合可以解決一類求樹上多條路徑信息並的問題，詳見 數據結構/樹分塊。

與莫隊結合

詳見 雜項/莫隊配合 bitset。

計算高維偏序

詳見 FHR 課件。

參考資料與註釋

  1. libstdc++: SGI STL extensions ↩

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

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