# 【C++ 筆記】bitset 容器，C++ 二進位運算的絕佳利器
目錄（Table of Contents）：
[TOC]
---
很感謝你點進來這篇文章。
你好，我並不是什麼 C++、程式語言的專家，所以本文若有些錯誤麻煩請各位鞭大力一點，我極需各位的指正及指導！！本系列文章的性質主要以詼諧的口吻，一派輕鬆的態度自學程式語言，如果你喜歡，麻煩留言說聲文章讚讚吧！
## 什麼是 bitset？
`std::bitset<N>` 是 C++ STL（位於標頭檔 `<bitset>`）中，一個用來表示固定長度為 $N$ 位元（bits）的位元序列（bit sequence）的類別模版。
假設 $N = 16$ ，那就表示有 16 位元，數字 1 就會表示成 "0000000000000001"。
bitset 也是 C++ 當中的一種容器，這個容器能夠做到單獨、有效的去操作每一個位元，也能解決位元運算、實現二進位表示法的工具，這也是為什麼需要用到它的原因。
## 使用 bitset
bitset 在使用之前需要引入標頭檔 `<bitset>`，另外以下是其基本語法：
```cpp=
bitset<n> name;
```
其中 `n` 是固定的位元數，而 `name` 則為 bitset 容器的名稱。
### 初始化 bitset
可以透過建構子 `()` 對 bitset 進行初始化的動作，如下程式碼做的動作：
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <16> a(5); // 十進位數字 5
cout << a;
return 0;
}
```
Output：
```
0000000000000101
```
由於給予的初始值是十進位的數字 5，所以理所當然會輸出 2 進位 16 bits 的 5。
初始值不一定是給予十進位數字，也可以是二進位字串：
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <16> a("101");
cout << a;
return 0;
}
```
Output：
```
0000000000000101
```
你也可以選擇不加上初始值，那預設就會是 16 個 0：
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <16> a;
cout << a;
return 0;
}
```
Output：
```
0000000000000000
```
最後是比較奇特的自訂字元初始化，可以指定哪個字元代表 1，哪一個代表 0：
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset<16> a("ooxxxoxoxoxoxoox", 16, 'o', 'x'); // o 指定 0, x 指定 1
cout << a;
return 0;
}
```
Output：
```
0011101010101001
```
### 存取 bitset 的單一位元
使用 `[]` 運算子，裡面索引一樣是從 0 開始。
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <6> a("101");
cout << a[0]; // 存取第一個位元 1
return 0;
}
```
Output：
```
1
```
## bitset 常用函數
### 設定、重置操作
- `set()`：設定位元為 1。
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <6> a(32); // 32 = 100000
a.set(); // 設定所有位元為 1
a.set(2); // 設定第 2 位為 1
a.set(2, 0); // 設定第 2 位為 0
cout << a;
return 0;
}
```
Output：
```
111011
```
- `reset()`：重置位元為 0。
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <6> a(32); // 32 = 100000
a.reset(); // 所有位元設為 0
cout << "位元重置：" << a << endl;
a.set(); // 所有位元設為 1
a.reset(3); // 第 3 位設為 0
cout << "第三位是 0：" << a << endl;
return 0;
}
```
Output：
```
位元重置：000000
第三位是 0：110111
```
- `flip()`：翻轉位元（0 變 1，1 變 0）。
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <6> a(32); // 32 = 100000
a.flip(); // 翻轉所有位元 -> 011111
a.flip(1); // 翻轉第 32 位 -> 011101
cout << a;
return 0;
}
```
Output：
```
011101
```
### 查詢操作
- `test()`：測試某位元是否為 1。
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <6> a(32); // 32 = 100000
cout << "第一位是 1 嗎？" << (a.test(0) ? "Yes" : "No");
return 0;
}
```
Output：
```
第一位是 1 嗎？No
```
- `count()`：計算有多少個 1。
這蠻好用的，有些題目會考有多少個 1，直接用上這個就對了。
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <6> a(32); // 32 = 100000
cout << "有多少個 1？" << a.count();
return 0;
}
```
Output：
```
有多少個 1？1
```
- `size()`：回傳 bitset 的大小，這就不提供範例了。
- `any()`：是否有任何位元為 1。
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <6> a(32); // 32 = 100000
cout << "有1嗎？" << (a.any() ? "Yes" : "No");
return 0;
}
```
Output：
```
全都是1？Yes
```
- `all()`：是否所有位元都為 1。
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <6> a(32); // 32 = 100000
cout << "全都1？" << (a.all() ? "Yes" : "No");
return 0;
}
```
Output：
```
全都1？No
```
- `none()`：是否所有位元都為 0。
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <6> a(32); // 32 = 100000
cout << "全都0？" << (a.none() ? "Yes" : "No");
return 0;
}
```
Output：
```
全都0？No
```
## 型態轉換操作
- `to_string()`：轉成字串。
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <6> a(32); // 32 = 100000
string str = a.to_string();
cout << str;
return 0;
}
```
Output：
```
100000
```
- `to_ulong()`：轉成 unsigned long。
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <6> a(32); // 32 = 100000
unsigned long val = a.to_ulong();
cout << val;
return 0;
}
```
Output：
```
32
```
- `to_ullong()`：轉成 unsigned long long。
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset <6> a(32); // 32 = 100000
unsigned long long val = a.to_ullong();
cout << val;
return 0;
}
```
Output：
```
32
```
## 支援的位元運算子
Bitset 支援以下這幾種位元運算子：
- `&`：AND
- `|`：OR
- `^`：XOR
- `~`：NOT
- `>>=`：右移賦值運算子。
- `<<=`：左移賦值運算子。
- `&=`：AND 賦值運算子。
- `|=`：OR 賦值運算子。
- `^=`：XOR 賦值運算子。
範例：
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset<8> b1("10101010");
bitset<8> b2("11110000");
bitset<8> result = b1 & b2;
cout << result;
return 0;
}
```
Output：
```
10100000
```
也可以做比較運算：
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main(){
bitset<8> b1("10101010");
bitset<8> b2("11110000");
if (b1 == b2){
cout << "equal";
}
else{
cout << "not equal";
}
return 0;
}
```
Output：
```
not equal
```
## 為什麼要用 bitset？
首先是空間效率使用的問題，bitset 一個元素只占一個 bit 而已，而一個 char 是一個 byte，等於 8 個 bit，就可見他的使用效率，比什麼 bool 陣列來得更省記憶體。
再來是高效能的操作，因為在編譯時期（Runtime）就確定大小，能進行高效的位元儲存和操作。
最後就是因為他蠻好用的，不用自己手搓完整的位元運算出來。
## 習題練習
### Uva 10019 - Funny Encryption Method
Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=960
Zerojudge：https://zerojudge.tw/ShowProblem?problemid=e545
PDF Source：https://onlinejudge.org/external/100/10019.pdf
範例程式碼：
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while (t--){
int N;
cin >> N;
bitset <16> b1(N);
int N2 = stoi(to_string(N), nullptr, 16);
bitset <16> b2(N2);
cout << b1.count() << " " << b2.count() << "\n";
}
return 0;
}
```
### Uva 10931 - Parity
Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=1872
Zerojudge：https://zerojudge.tw/ShowProblem?problemid=a132
PDF Source：https://onlinejudge.org/external/109/10931.pdf
範例程式碼：
```cpp=
#include <bits/stdc++.h>
using namespace std;
int count_ones(int x) {
int count = 0;
while (x > 0) {
count += x & 1;
x >>= 1;
}
return count;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int I;
while (cin >> I && I != 0){
bitset<32> binary(I);
string result = binary.to_string();
auto f1 = result.find('1');
result = result.substr(f1);
cout << "The parity of " << result << " is " << count_ones(I) << " (mod 2)." << "\n";
}
return 0;
}
```
## 總結
`std::bitset<N>` 是 C++ STL 中用來表示固定長度 N 位元的容器，需要引入 `<bitset>` 標頭檔。它能有效地操作每一個位元，是處理位元運算和二進位表示的實用工具。
四種初始化方法：
1. 十進位數字：`bitset<16> a(5)` 輸出 `0000000000000101`
2. 二進位字串：`bitset<16> a("101")` 輸出 `0000000000000101`
3. 預設值（全為 0）：`bitset<16> a` 輸出 `0000000000000000`
4. 自訂字元：`bitset<16> a("ooxxxoxox", 16, 'o', 'x')` 可指定哪個字元代表 0 或 1
存取位元：
- 使用 `[]` 運算子，索引從 0 開始，例如 `a[0]` 存取第一個位元。
設定與重置：
1. `set()`：將位元設為 1（可指定位置或全部）
2. `reset()`：將位元設為 0（可指定位置或全部）
3. `flip()`：翻轉位元（0 變 1，1 變 0）
查詢操作：
1. `test(pos)`：測試指定位元是否為 1
2. `count()`：計算有多少個 1
3. `any()`：檢查是否有任何位元為 1
4. `all()`：檢查是否所有位元都為 1
5. `none()`：檢查是否所有位元都為 0
6. `size()`：回傳 bitset 大小
型態轉換：
1. `to_string()`：轉換為字串
2. `to_ulong()`：轉換為 unsigned long
3. `to_ullong()`：轉換為 unsigned long long
## 參考資料
[C++ Bitset and its Application - GeeksforGeeks](https://www.geeksforgeeks.org/cpp/cpp-bitset-and-its-application/)
[C++ std::bitset 用法與範例 | ShengYu Talk](https://shengyu7697.github.io/std-bitset/)
[C++ 容器类 `<bitset>` | 菜鸟教程](https://www.runoob.com/cplusplus/cpp-libs-bitset.html)
Sign in with Wallet
Connect another wallet