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;
}