【C++ 筆記】bitset 容器，C++ 二進位運算的絕佳利器

很感謝你點進來這篇文章。

你好，我並不是什麼 C++、程式語言的專家，所以本文若有些錯誤麻煩請各位鞭大力一點，我極需各位的指正及指導！！本系列文章的性質主要以詼諧的口吻，一派輕鬆的態度自學程式語言，如果你喜歡，麻煩留言說聲文章讚讚吧！

什麼是 bitset？

std::bitset<N> 是 C++ STL（位於標頭檔 <bitset>）中，一個用來表示固定長度為 $N$ 位元（bits）的位元序列（bit sequence）的類別模版。

假設 $N = 16$ ，那就表示有 16 位元，數字 1 就會表示成 “0000000000000001”。

bitset 也是 C++ 當中的一種容器，這個容器能夠做到單獨、有效的去操作每一個位元，也能解決位元運算、實現二進位表示法的工具，這也是為什麼需要用到它的原因。

使用 bitset

bitset 在使用之前需要引入標頭檔 <bitset>，另外以下是其基本語法：

1
bitset<n> name;

其中 n 是固定的位元數，而 name 則為 bitset 容器的名稱。

初始化 bitset

可以透過建構子 () 對 bitset 進行初始化的動作，如下程式碼做的動作：

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <bitset>

using namespace std;

int main(){
    bitset <16> a(5); // 十進位數字 5
    cout << a;
    return 0;
}

Output：

1
0000000000000101

由於給予的初始值是十進位的數字 5，所以理所當然會輸出 2 進位 16 bits 的 5。

初始值不一定是給予十進位數字，也可以是二進位字串：

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <bitset>

using namespace std;

int main(){
    bitset <16> a("101");
    cout << a;
    return 0;
}

Output：

1
0000000000000101

你也可以選擇不加上初始值，那預設就會是 16 個 0：

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <bitset>

using namespace std;

int main(){
    bitset <16> a;
    cout << a;
    return 0;
}

Output：

1
0000000000000000

最後是比較奇特的自訂字元初始化，可以指定哪個字元代表 1，哪一個代表 0：

1
2
3
4
5
6
7
8
9
10
#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：

1
0011101010101001

存取 bitset 的單一位元

使用 [] 運算子，裡面索引一樣是從 0 開始。

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <bitset>

using namespace std;

int main(){
    bitset <6> a("101");
    cout << a[0]; // 存取第一個位元 1
    return 0;
}

Output：

1
1

bitset 常用函數

設定、重置操作

  • set()：設定位元為 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
#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：

1
111011
  • reset()：重置位元為 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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：

1
2
位元重置：000000
第三位是 0：110111
  • flip()：翻轉位元（0 變 1，1 變 0）。
1
2
3
4
5
6
7
8
9
10
11
12
#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：

1
011101

查詢操作

  • test()：測試某位元是否為 1。
1
2
3
4
5
6
7
8
9
10
#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
第一位是 1 嗎？No
  • count()：計算有多少個 1。

這蠻好用的，有些題目會考有多少個 1，直接用上這個就對了。

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <bitset>

using namespace std;

int main(){
    bitset <6> a(32); // 32 = 100000
    cout << "有多少個 1？" << a.count();
    return 0;
}

Output：

1
有多少個 1？1

  • size()：回傳 bitset 的大小，這就不提供範例了。

  • any()：是否有任何位元為 1。

1
2
3
4
5
6
7
8
9
10
#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
全都是1？Yes
  • all()：是否所有位元都為 1。
1
2
3
4
5
6
7
8
9
10
#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
全都1？No
  • none()：是否所有位元都為 0。
1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <bitset>

using namespace std;

int main(){
    bitset <6> a(32); // 32 = 100000
    cout << "全都0？" << (a.none() ? "Yes" : "No");
    return 0;
}

Output：

1
全都0？No

型態轉換操作

  • to_string()：轉成字串。
1
2
3
4
5
6
7
8
9
10
11
#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：

1
100000
  • to_ulong()：轉成 unsigned long。
1
2
3
4
5
6
7
8
9
10
11
#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：

1
32
  • to_ullong()：轉成 unsigned long long。
1
2
3
4
5
6
7
8
9
10
11
#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：

1
32

支援的位元運算子

Bitset 支援以下這幾種位元運算子：

  • &：AND
  • |：OR
  • ^：XOR
  • ~：NOT
  • >>=：右移賦值運算子。
  • <<=：左移賦值運算子。
  • &=：AND 賦值運算子。
  • |=：OR 賦值運算子。
  • ^=：XOR 賦值運算子。

範例：

1
2
3
4
5
6
7
8
9
10
11
12
#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：

1
10100000

也可以做比較運算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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：

1
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

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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

C++ std::bitset 用法與範例 | ShengYu Talk

C++ 容器类 <bitset> | 菜鸟教程