目录
1.简介
2.定义与初始化
3.操作接口
4.高级用法
5.线程安全性
6.std::bitset的应用
6.1快速判断某个数据是否在一个集合中
6.2.求两个集合的交集、并集等
6.3.数据统计次数
7.总结
类模板 表示一个 位的固定大小序列。可以用标准逻辑运算符操作 ，并将它与字符串和整数相互转换。对于字符串表示和移位操作的列举方向来说，这个序列被当做最低索引元素位于右侧，类似于整数的二进制表示。这个类提供了一些方便的方法来操作位，例如设置、重置、翻转位等。
满足可复制构造 (CopyConstructible) 及可复制赋值 (CopyAssignable) 的要求。
下面是 类型的创建方式：
类似于vector，bitset类是一种类模板；而与vector不一样的是bitset类型对象的区别仅在其长度而不在其类型。在定义bitset时，要明确bitset含有多少位，须在尖括号内给出它的长度值：
多种bitset操作用来测试或设置bitset对象中的单个或多个二进制位：
这些函数使得 成为处理位级别数据的强大工具。示例如下：
输出：
是一个非常强大的工具，可以用于处理位级别的操作。除了基本的设置和获取位之外，它还提供了一些高级的功能。以下是一些 的高级用法：
1.位操作符： 支持位操作符 、、 和 ，以及相应的复合赋值操作符 、 和 。这些操作符可以用于执行位级别的 AND、OR、XOR 和 NOT 操作。
2.位移操作符： 支持位移操作符 和 ，以及相应的复合赋值操作符 和 。这些操作符可以用于执行位级别的左移和右移操作。
3.比较操作符： 支持比较操作符 和 。这些操作符可以用于比较两个 是否相等。
4.其他有用的成员函数：std::bitset 还提供了一些其他有用的成员函数，如 count()（返回设置的位数）、size()（返回位数）、test(size_t pos)（检查指定位置的位是否设置）、any()（检查是否有位设置）、none()（检查是否没有位设置）和 flip()（反转所有位）等。
本身是线程不安全的。在C++标准库中，除非特别说明，否则大多数容器和工具都不是线程安全的。这意味着如果你在多线程环境中直接修改或访问同一个 对象，而没有使用适当的同步机制（如互斥锁、条件变量、原子操作等），则可能会导致数据竞争和其他并发问题。
数据竞争是指两个或更多的线程并发访问同一个内存位置，并且至少有一个线程是写入操作，且这些线程之间没有使用同步来协调这些访问。数据竞争会导致未定义的行为，包括但不限于程序崩溃、数据损坏或不可预测的结果。
如果你需要在多线程环境中使用 ，你应该确保对它的访问是同步的。这可以通过以下几种方式实现：
1）使用互斥锁（如 ）来保护对 的访问。在访问 之前锁定互斥锁，在访问完成后释放锁。这可以确保在任何时候只有一个线程可以修改或读取 。
2）使用原子操作（如 ）来安全地修改 中的单个位。但是，请注意， 本身并不提供原子操作，因此你可能需要将 转换为其他支持原子操作的数据结构，或者只使用 的一部分，并确保对该部分的访问是原子的。
3）避免在多个线程之间共享 对象。相反，每个线程可以拥有自己的 副本，并在需要时与其他线程交换或合并数据。这种方法可能会增加内存使用，但可以避免并发问题。
示例1：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
根据这个问题，我们可以用什么方法来解决呢？？？我们可以很迅速地想到一下方法：
方法1：排序+二分查找
方法2：将整数丢进哈希表或者红黑树中
看似好像都能解决这个问题，但是我们来审视一下这个问题的关键——内存
1G=1024MB=1024*1024KB=1024*1024*1024Byte 约等于10亿Byte，也就是说40亿个数大约需要16G内存！！没有办法将数据一次性放到内存去处理。
（1）分析方法1：如果我们将数据分在不同的文件里，我们可以用归并排序去完成文件之间的排序，但是无法使用二分查找法，因为没有办法通过下标去直接访问元素！！！
（2）分析方法2：问题就是所需要的内存太大了，光是数据就16G了，更何况红黑树和哈希表的底层的封装还需要一定的损耗，我们如果要使用的话也只能是一部分一部分丢进容器，然后再删掉丢下一部分，这样一方面的问题是我们其实在一开始丢进容器的时候就可以去做比对了，没有必要丢到容器里，另一方面的问题就是不适应需要多次查找比对的场景。
因此上面两种方法都是不太现实的，但是有一种数据结构可以帮助我们解决这个问题，那就是位图——通过哈希函数中的直接定址法确定整型在不在的模型（就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。）
所以方法3：用std::bitset去解决
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。
位图是一种直接定址法的哈希，因此效率很高，用O(1)就可以探测到对应位是0还是1，效率非常高，因此可以快速判断。
利用每一个比特位的0或1的情况，来判断数在不在，所以40亿不重复的数，开辟2^32-1个比特位，转化为G，也就512m，内存很小。
我们来看代码实现：
示例2：给定100亿个整数，设计算法找到只出现一次的整数？
统计次数的话，那么就需要两个位图来实现，两个比特位来统计00（0次），01（1次），10（2次及以上）。
直接上代码：
一个数如果在两个位图中的同一位置都是0，那么说明就是0次 ，再进来的数就要将00第二位set为01，表示出现一次，后面同理可得。
示例1：给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
首先我们知道，整数的范围最大是42亿多，所以100亿个整数中，一定存在许多重复的整数。
所以将文件中的数据都放入位图中，只看 存在或者不存在两种状态，这就自动去掉了重复的数，某一位一直是1。只有512MB，可以存入内存中进行处理。
然后两个位图进行相与操作，同时为1说明是交集。
示例：实现一个算法，确定一个字符串 的所有字符是否全都不同。
示例 1：
输入: = "leetcode" 输出: false
示例 2：
输入: = "abc" 输出: true
限制：
- 仅包含小写字母
- 如果你不使用额外的数据结构，会很加分。
直接上代码：
是 C++ 标准库中的一个模板类，用于处理固定大小的位集。它提供了一个方便的方式来操作位序列，如设置、清除、翻转和测试位。下面是 的一些主要优点和缺点：
优点
1）简洁易用的位操作： 提供了许多成员函数，如 , , , , , 等，这些函数使得位操作变得简单且易于理解。
2）固定大小：当你需要一个固定大小的位集时， 是一个非常合适的选择。你可以通过模板参数指定 的大小，并在整个程序中保持这个大小不变。
3）高效存储： 通常比使用 数组或 整数来存储位集更节省内存。这是因为 内部使用了一种紧凑的存储方式，并且避免了 类型可能带来的内存对齐问题。
4）类型安全：使用 可以确保你只操作指定大小的位集，这有助于防止越界访问等错误。
5）可读性：对于涉及位操作的代码，使用 可以提高代码的可读性。例如，你可以使用 的 函数将位集转换为字符串，以便在调试或日志记录时输出。
缺点
1）固定大小限制： 的大小在创建时是固定的，并且之后不能更改。这意味着如果你需要处理可变大小的位集，那么 可能不是最佳选择。在这种情况下，你可能需要使用 或其他数据结构。
2）性能开销：虽然 在内存使用方面很高效，但在某些情况下，它可能会引入一些性能开销。例如，当你需要频繁地访问或修改 中的位时，直接操作 整数可能会更快，因为整数操作通常可以在硬件级别上得到优化。
3）不支持动态扩展：由于 的大小是固定的，因此它不支持动态扩展。如果你需要在运行时增加或减少位集的大小，那么你需要创建一个新的 并复制数据（如果可能的话）。
4）模板参数限制： 的大小是一个非类型模板参数，这意味着它必须是一个常量表达式。在某些情况下，你可能无法在编译时确定位集的大小，这将限制你使用 的能力。
std::bitset - cppreference.com
推荐阅读：
布隆过滤器基本原理与使用-CSDN博客
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/14894.html