bitsetc++

一、bitset場景

bitset是c++標準庫中的一個類，它表示二進制位的集合，其最大的優點就是可以在代碼中快速高效地處理二進制。

bitset通常應用於各種算法問題中，例如圖論中的狀態壓縮、編碼解碼，壓縮算法中的哈夫曼編碼等等。同時，bitset還能夠應用於大數據處理、數據篩選等場景下。

例如，當一種結構體需要根據某種屬性進行排序時，如果該屬性是bool類型，那麼使用bitset可以將排序的效率提升很多。

二、bitset長度

bitset的長度是指其中的二進制位個數，一般為一個整數類型除以8的結果。既然bitset的單位是二進制位，因此它的長度只能是8的倍數！

對於C++標準庫中的bitset，長度是個常數。示例代碼如下：

#include 
#include 

int main() {
    std::bitset bs; //長度是8
    std::cout << bs.count() << std::endl; //輸出0
    return 0;
}

三、bitset操作

bitset本質上就是一個二進制數，因此它可以進行多種二進制操作：

1. set和reset

set和reset操作分別將bitset的某個二進制位設為1或0。

#include 
#include 

int main() {
    std::bitset bs(42); //二進制表示為00101010
    bs.set(1); //將第1位（從右往左數，從0開始）設置為1
    bs.reset(3); //將第3位設置為0
    std::cout << bs.to_ulong() << std::endl; //輸出結果為46，二進制表示為00101110
    return 0;
}

2. flip

flip操作將bitset的某個二進制位取反，即1變為0，0變為1。

#include 
#include 

int main() {
    std::bitset bs(42); //二進制表示為00101010
    bs.flip(1); //將第1位（從右往左數，從0開始）取反
    std::cout << bs.to_ulong() << std::endl; //輸出結果為46，二進制表示為00101110
    return 0;
}

3. 數組操作

由於bitset本質上就是一個二進制數，因此它也可以被看成一個bool型數組，數組的下標對應於二進制數的位置。

#include 
#include 

int main() {
    std::bitset bs(42); //二進制表示為00101010
    std::cout << bs[1] << std::endl; //輸出1
    std::cout << bs[3] << std::endl; //輸出0
    bs[3] = 1; //將第3位（從右往左數，從0開始）設置為1
    std::cout << bs.to_ulong() << std::endl; //輸出58，二進制表示為00111010
    return 0;
}

四、bitset存儲原理

bitset在內存中的存儲和使用也非常特殊，在標準庫中的實現一般採用一個unsigned long long的數組進行存儲。舉例來說，如果bitset的長度為64，那麼就需要一個unsigned long long來存儲；如果bitset的長度為80，那麼就需要兩個unsigned long long來存儲。

五、bitset乘法

bitset相乘只能對其長度以及一些位數樣式相同的bitset進行。

#include 
#include 

int main() {
    std::bitset b1(42);  //0010 1010
    std::bitset b2(99);  //0110 0011
    std::bitset b3;
    b3 = b1 & b2;  //0010 0010
    std::cout << b3.to_ulong() << std::endl;  //輸出34
    b3 = b1 | b2;  //0110 1011
    std::cout << b3.to_ulong() << std::endl;  //輸出107
    b3 = b1 ^ b2;  //0100 1001
    std::cout << b3.to_ulong() << std::endl;  //輸出73
    return 0;
}

六、bitset查詢連續1個數

bitset可以快速查找其中連續1的個數，使用count方法即可。

#include 
#include 

int main() {
    std::bitset b1(42);  //0010 1010
    std::bitset b2(58);  //0011 1010
    std::cout << b1.count() << std::endl;  //輸出3
    std::cout << b2.count() << std::endl;  //輸出4
    return 0;
}