第17章标準庫特殊設施 - bitset 類型

17.2 BITSET類型

标準庫定義了

bitset

類，使得位運算的使用更為容易，并且能夠處理超過最長整型類型大小的位集合。

bitset

類定義在頭檔案

bitset

中。

17.2.1 定義和初始化bitset

bitset

類是一個類模闆，它類似

array

類，具有固定的大小。當我們定義一個

bitset

時，需要聲明它包含多少個二進制位：

這條語句定義

bitvec

為一個包含 32 位的

bitset

。就像

vector

包含未命名的元素一樣，

bitset

中的二進制位也是未命名的，我們通過為止通路它們。二進制位的位置是從

開始編号的。是以，

bitvec

包含編号從

到

的 32個二進制位。編号從

開始的二進制位被稱為低位(low-order)，編号到

結束的二進制位被稱為高位(high-orderer)。

表17.2：初始化 `bitset` 的方法

bitset<n> b; b 有 n 位；每一位均為。此構造函數是一個 constexpr 。
bitset<n> b(u); b 是 unsigned logn long 值 u 的低 n 位的拷貝。如果 n 大于 unsigned long long 的大小，則 b 中超出 unsigned long long 的高位被置位。此構造函數是一個 constexpr 。
bitset<n> b(s, pos, m, zero, one); b 是 string s 從位置 pos 開始 m 個字元的拷貝。 s 隻能包含字元 zero 或 one；如果 s 包含任何其他字元，構造函數會抛出 invalid_argument 異常。字元在 b 中分别儲存為 zero 和 one。 pos 預設為， m 預設為 string::npos ，zero 預設為 '0' ，one 預設為 '1' 。
bitset<n> b(cp, pos, m, zeor, one); 與上一個構造函數相同，但從 cp 指向的字元數組中拷貝字元。如果未提供 m ，則 cp 必須指向一個 C 風格字元串。如果提供了 m ，則從 cp 開始必須至少有 m 個 zero 或 one 字元。

用 `unsigned` 值初始化 `bitset`

當使用一個整型值來初始化 bitset 時，此值将被轉換為 unsigned long long 類型并被當做位模式來處理。 bitset 中的二進制位将是此模式的一個副本。
如果 bitset 的大小大于一個 unsigned long long 中的二進制位數，則剩餘的高位被置為。
如果 bitset 的大小小于一個 unsigned long long 中的二進制位數，則隻使用給定值中的低位，超出 bitset 大小的高位被丢棄。

// bitvec1 比初始值小；初始值中的高位被丢棄
bitset<13> bitvec1(0xbeef);  
    // 原本的二進制位序列為           1011111011101111
    // 高位被丢棄後的二進制位序列         1111011101111

// bitvec2 比初始值小；它的高位被置為 0
bitset<20> bitvec2(0xbeef);
    // 原本的二進制位序列為           1011111011101111
    // 高位被置為0後的二進制位序列 00001011111011101111

// 在 64 位機器中，long long 0ULL 是 64 個 0 比特，是以 ~0ULL 是 64 個 1
bitset<128> bitvec3(~0ULL); // 0~63位為 1；63~127位為 0

從一個 `string` 初始化 `bitset`

我們可以從一個

string

或一個

字元數組指針

來初始化

bitset

。

兩種情況下，字元都直接表示位模式。

當我們使用字元串表示數時，字元串中下标最小的字元對應高位，反之亦然：

如果

string

包含的字元數比

bitset

少，則

bitset

的高位被置為

。

Note:

string

的下标編号習慣于

bitset

恰好相反：

string

中下标最大的字元（最右字元）用來初始化

bitset

中的低位（下标為

的二進制位）。當使用一個

string

初始化一個

bitset

時，要記住這個差别。

我們不必使用整個

string

來作為

bitset

的初始值，可以隻用一個子串作為初始值；

string str("1111111000000011001101");
bitset<32> bitvec5(str, 5, 4);      // 從 str[5] 開始的四個二進制位，1100
bitset<32> bitvec6(str, str.size() - 4); // 使用最後四個字元（字元數組指針）

分析：

bitvec5 用 str 中從 str[5] 開始的長度為 4 的子串進行初始化。與往常一樣，子串的最右字元表示最低位。是以， bitvec5 中第 3 位到第位被設定為 1100 ，剩餘位被設定為。
傳遞給 bitvec6 的初始值是一個 string 和一個開始位置，是以 bitvec6 用 str 中倒數第四個字元開始的子串進行初始化。 bitvec6 中剩餘二進制位被初始化為。

第17章标準庫特殊設施 - bitset 類型

練習 17.9：解釋下列每個

bitset

對象所包含的位模式：

(a)

bitset<64> bitvec(32);

bitvec

為

位，第

位為

，剩餘位為

。// 疑問：這裡不确定是

位還是

位

(b)

bitset<32> bv(1010101);

bv

為 32 位，0、2、4、6 這 4 位為

，剩餘位為

。

string bstr; cin >> bstr; bitset<8>bv(bstr);

bv

為

位，用

bstr

來對其進行初始化。若讀入的字元串不是單純的二進制字元串，程式會抛出

invalid_argument

異常。

17.2.2 bitset操作

表17.3：

bitset

操作

`b.any()`	`b` 中是否存在置位的二進制位
`b.all()`	`b` 中所有位都置位了嗎
`b.none()`	`b` 中不存在置位的二進制位嗎
`b.count()`	`b` 中置位的位數
`b.size()`	`b` 中置位的位數
`b.size()`	一個 `constexpr` 函數，傳回 `b` 中的位數
`b.test(pos)`	若 `pos` 位置的位是置位的，則傳回 `true` ，否則傳回 `false`
`b.set(pos, v)`	将位置 `pos` 處的位設定為 `bool` 值 `v` 。 `v` 預設為 `true` 。
`b.set()`	如果未傳遞實參，則将 `b` 中所有位置位
`b.reset(pos)`	将位置 `pos` 處的位複位或将 b 中所有位複位
`b.reset()`
`b.flip(pos)`	改變位置 `pos` 處的位的狀态或改變 `b` 中每一位的狀态
`b[pos]`	通路 `b` 中位置 `pos` 處的位；如果 `b` 是 `const` 的，則當該位置位時 `b[pos]` 傳回一個 `bool` 值 `true` ，否則傳回 `false`
`b.to_ulong()`	傳回一個 `unsigned long` 或一個 `unsigned long long` 值，其位模式與 `b` 相同。如果 `b` 中位模式不能放入指定的結果類型，則抛出一個 `overflow_error` 異常
`b.to_ullong()`
`b.to_string(zero, one)`	傳回一個 `string` ，表示 `b` 中的位模式。 `zero` 和 `one` 的預設值分别為和 1，用來表示 `b` 中的和 `1`
`os << b`	将 `b` 中二進制位列印為字元 `1` 或，列印到流 `os`
`is >> b`	從 `is` 讀取字元存入 `b` 。當下一個字元不是 `1` 或時，或是已經讀入 `b.size()` 個位時，讀取過程停止

bitset<32> bitvec(1U);				// 32 位；低位為 1，剩餘位為 0
bool is_set = bitvec.any();			// true，因為有1位置位
bool is_not_set = bitvec.none();	// false，因為有1位置位
bool all_set = bitvec.all();		// false，因為隻有1位置位
size_t onBits = bitvec.count();		// 傳回 1
size_t sz = bitvec.size();			// 傳回 32
bitvec.flip();		// 翻轉 bitvec 中的所有位
bitvec.reset();		// 将所有位複位
bitvec.set();		// 将所有位置位

當 bitset 對象的一個或多個位置位（即，等于 1）時，操作 any 傳回 true 。當所有位置位時，操作 all 傳回 true 。
當所有位複位時， none 傳回 true 。
操作 count 和 size 傳回 size_t 類型的值，分别表示對象中置位的位數或總位數。函數 size 是一個 constexpr 函數

成員

flip

set

reset

及

test

允許我們讀寫指定位置的位：

bitvec.flip(0);					// 翻轉第一位
bitvec.set(bitvec.size() - 1);	// 置位最後一位
bitvec.set(0, 0);	// 複位第一位
bitvec.reset(i);	// 複位第 i 位
bitvec.test(0);		// 傳回 false，因為第一位是複位的

下标運算符對

const

屬性進行了重載。

const

版本的下标運算符在指定位置位時傳回

true

，否則傳回

false

。非

const

版本傳回

bitset

定義的一個特殊類型，它允許我們操縱指定位的值：

bitvec[0] = 0;			// 将第一位複位
bitvec[31] = bitvec[0];	// 将最後一位設定為與第一位一樣
bitvec[0].flip();		// 翻轉第一位
~bitvec[0];				// 等價操作，也是翻轉第一位
bool b = bitvec[0];		// 将 bitvec[0] 的值轉換為 bool 類型

提取 `bitset` 的值

沒看懂 P644

`bitset` 的 IO 運算符

輸入運算符從一個輸入流讀取字元，儲存到一個臨時的

string

對象中。

直到讀取的字元數達到對應

bitset

的大小時，

或是遇到不是

或

的字元時，

或是遇到檔案尾或輸入錯誤時，讀取過程才停止。

随即用臨時

string

對象來初始化

bitset

。

如果讀取的字元數小于

bitset

的大小，則與往常一樣，高位将被置位

。

// 輸出運算符列印一個 bitset 對象的位模式
bitset<16> bits;
cin >> bits; // 從 cin 讀取最多 16 個 0 或 1
cout << "bits: " << bits << endl; // 列印剛剛讀取的内容

使用 `bitset`

為了說明如何使用 bitset，用 bitset 代替 unsigned long 表示 30 個學生的測驗結果——“通過/失敗”：

bool status;
// 使用位運算符的版本
unsigned long quizA = 0;    // 此值被當做位集合使用
quizA |= 1UL << 27;         // 指出第 27 個學生通過了測驗
status = quizA & (1UL << 27); // 檢查第 27 個學生是否ton過了測驗
quizA &= ~(1UL << 27);      // 第 27 個學生未通過測驗

// 使用标準庫類 bitset 完成等價的工作
bitset<30> quizB;           // 每個學生配置設定一位，所有為都被初始化為 0
quizB.set(27);              // 指出第 27 個學生通過了測驗
status = quizB[27];         // 檢查第 27 個學生是否通過了測驗
quizB.reset(27);            // 第 27 個學生未通過測驗

練習17.10：使用序列 1、2、3、5、8、13、21 初始化一個 bitset，将這些位置置位。對另一個 bitset 進行預設初始化，并編寫一小段程式将其恰當的位置位。

/*練習17.10：使用序列 1、2、3、5、8、13、21 初始化一個 bitset，将這些位置置位。
對另一個 bitset 進行預設初始化，并編寫一小段程式将其恰當的位置位。*/

#include <iostream>
#include <bitset>

using namespace std;

int main(int argc, char **argv)
{
    unsigned bp = 2 | (1 << 2) | (1 << 5) | (1 << 8) | (1 << 13) | (1 << 21);
    bitset<32> bv(bp);
    cout << bv << endl;

    bitset<32> bv1;
    bv1.set(1); bv1.set(2); bv1.set(3); bv1.set(5);
    bv1.set(8); bv1.set(13); bv1.set(21);
    cout << bv1 << endl;

    return 0;
}

練習17.11：定義一個資料結構，包含一個整型對象，記錄一個包含10個問題的真假測驗的解答。如果測驗包含100道題，你需要對資料結構做出什麼改變（如果需要的話）。

【出題思路】本題練習

bitset

的定義和使用。

【解答】如果使用整數儲存測驗解答，那麼對于

個問題的測驗，隻需一個短整型對象即可。

如果改為

道題，則需

個

位整數或是

個

位整數。而且修改的并不僅僅是資料結構，所有對整型數進行操作來修改解答和評分的代碼都要相應進行修改，工作量很大。

采用

bitset

則有很明顯的優勢，當題目數改變時，我們隻需改變

bitset

的規模，而操作

bitset

來完成改答案、評分的代碼則隻需進行很小的修改。

最佳的方式是定義一個類模闆，它有一個模闆參數表示題目數，有一個

bitset

成員儲存解答，然後定義一些成員函數來完成改答案、評分等操作。當題目數發生變化，我們隻需執行個體化一個新版本即可，其他代碼均無須改動。

練習17.12：使用前一題中的資料結構，編寫一個函數，它接受一個問題編号和一個表示真／假解答的值，函數根據這兩個參數更新測驗的解答。

練習17.13：編寫一個整型對象．包含真／假測驗的正确答案．使用它來為前兩題中的資料結構生成測驗成績。

【出題思路】本題練習

bitset

的定義和使用。

/**
練習17.12：使用前一題中的資料結構，編寫一個函數，它接受一個問題編号和一個表示真／假解答的值，函數根據這兩個參數更新測驗的解答。

練習17.13：編寫一個整型對象．包含真／假測驗的正确答案．使用它來為前兩題中的資料結構生成測驗成績。
*/

#include <iostream>
#include <bitset>

using namespace std;

template <size_t N>
class exam {
public:
    exam() : s() {}
    size_t get_size() { return N; }
    void set_solution(size_t n, bool b) { s.set(n, b); }
    bitset<N> get_solution() const { return s; }
    size_t score (const bitset<N> &a);
private:
    bitset<N> s;
};

template <size_t N>
size_t exam<N>::score(const bitset<N> &a)
{
    size_t ret = 0;

    for (size_t i = 0; i < N; i++)
        if (s[i] == a[i])
            ret++;
    return ret;
}

int main (int argc, char **argv)
{
    exam<80> e;
    e.set_solution(0, 1);
    e.set_solution(79, 1);
    cout << e.get_solution() << endl;

    bitset<80> a;
    cout << e.get_size() << " problems, you've got " << e.score(a) << " points." << endl;
    
    return 0;
}
/* Output:
10000000000000000000000000000000000000000000000000000000000000000000000000000001
80 problems, you've got 78 points.
*/

第17章标準庫特殊設施 - bitset 類型

17.2 BITSET類型

17.2.1 定義和初始化bitset

表17.2：初始化 `bitset` 的方法

用 `unsigned` 值初始化 `bitset`

從一個 `string` 初始化 `bitset`

17.2.2 bitset操作

提取 `bitset` 的值

`bitset` 的 IO 運算符

使用 `bitset`

繼續閱讀

C++Primer學習劄記_指針和const限定符

c++ primer 習題8.3

C++ primer 2.1.3練習及答案

C++标準庫順序容器C++順序容器 sequential container

C++ Primer學習之（7）——函數

C++ primer 讀書筆記--第一章快速入門

【足迹C++primer】51、面向對象程式設計概述基類和派生類的定義 Thinking！

【C++Primer】第11章關聯容器第11章關聯容器

C++Primer第3章字元串、向量和數組

c++ primer 第三章字元串、向量和數組命名空間的using聲明标準庫類型string标準庫類型vector疊代器數組

函數指針和typedef函數指針用法

C++類的拷貝控制成員（拷貝構造、拷貝指派、移動構造、移動指派和析構函數）

c++ primer 第五版閱讀筆記七第6章分支語句和邏輯操作符6.10 複習題

main() 處理指令行選項

【C++基礎之六】運算符的重載

第17章 标準庫特殊設施 - bitset 類型

17.2 BITSET類型

17.2.1 定義和初始化bitset

表17.2：初始化 bitset 的方法

用 unsigned 值初始化 bitset

從一個 string 初始化 bitset

17.2.2 bitset操作

提取 bitset 的值

bitset 的 IO 運算符

使用 bitset

繼續閱讀

第17章标準庫特殊設施 - bitset 類型

表17.2：初始化 `bitset` 的方法

用 `unsigned` 值初始化 `bitset`

從一個 `string` 初始化 `bitset`

提取 `bitset` 的值

`bitset` 的 IO 運算符

使用 `bitset`