---
# System prepended metadata

title: 【C++ 筆記】bitset 容器，C++ 二進位運算的絕佳利器
tags: [資料結構, 程式設計, C++, 競程, 字串處理, 程式語言, 計算機概論, CP]

---

# 【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)