概念位图是bitmap的缩写，bitmap是指按位存储某一状态，适用于大规模数据，该数据全部是不重复的简单数据。 通常用于确定某个数据是否不存在
例如，给你40亿个不重复的无符号整数，没有排序的，然后再给你一个数，如何快速判断这个数是否在那个40亿中
如果不看数据量，我们首先想到的一定是从一开始就按顺序遍历，但是这个数据量非常大，有40亿之多，遍历40亿次所消耗的时间和内存非常多。 但是，引入位图可以解决这样大量的数据检索问题。 调查是否有这个数所消耗的时间的复杂性是o(1)，如下所述，节约了32倍的容量。 看看位图的原理和代码实现
调查有原理的数量是否存在的话，就会得到其实是否存在的答案。 这种只回答是还是否的问题可以用二进制位表示。 1表示该数存在，相反，0表示该数不存在。 位图中的每个数据单元都是1位，通常以32位4字节存储数据，但现在可以以1字节“存储数据”，在空间上减少了约32倍的容量。 例如，40G的数据以1.3G保存。 但是，我们平时操作的数据类型最小为1字节，不能直接对位操作，所以可以通过位运算操作数据。 让我们看看数据是如何存储在位图中的
这里显示了数组
intarr [ ]={ 1，2，4，5，7，10，11，14，16，17，21，23，24，28，29，31 }； 存储这些数据只需要一个字节
说明：现在很多机器都在小端序(little endian )或低地址中存储低位。 在一个整形数据中，第一个字节用于存储数字0-7，第二个字节存储数字8-15，第三个字节存储数字16-23，第四个字节存储数字24-31。 看看数字10是怎么保存的。 首先通过32填充模型，取馀数或10，然后将4字节中第10位的位置设为1，表示出现了该数字。 因为我们的机器是小端序，所以我们的各位从右边开始计算。 请参考下图
因此，将对应的位位置设为1即可。 但是，如果保存的数据很大呢？ 其实很简单。 可以将数组定义为位图。 如果该数字在0-31之间，则存储在0号下标的要素中进行操作。 如果在32-63之间，则在1号下标之间操作。 计算下标可以用模具32得到下标。
了解位图的原理后，让我们通过原理用代码实现位图
成员变量和构造函数:在位图实现中，成员变量可以在一个数组中实现。 这个数组有多大？ 在数组中增加一个整形空间可以存储更多的32个数字，从而为用户提供准确的数量。 此数量是数据量，是数量的最大范围。 这个数模上的32可以得到这个数组的大小，但是0到31型上的32是0，显然不适合开0个空间，所以range/32 1开1个空间大小的数组
33558www.Sina.com/:1:存储一个数字num需要三个步骤，第一个是计算该值对应的数组下标。 计算序列下标方式为idx=num/32； 第二步是计算对应整数的位位置bitIdx=num2的num。 第三步是将计算出的bite位置设置为1。 如上所述，要操作位，可以通过位运算进行操作。 1左移后可以和整数进行或运算
例如，假设bitIdx=5，则数据为10010011
将1.1向左移动5位==100000
2 .对数据和第一步计算的结果进行或运算
10010011 | 100000=10110011，在此将指定位置设置为1
33558www.Sina.com/:1:要确定是否存在单个数据，实际上类似于保存数据，但必须计算两个位置idx和bitIdx。 并且，根据这两个位置判断对应的位置是否为1，如果为1，则表示存在该数字。 你怎么判断？ 可以将数组下标为idx的整数向右移位bitIdx位，然后与1进行“和”运算。 1的情况存在，否则不存在
例如，假设bitIdx=5，则数据为10110011
1 .将数据向右移动5位00000101
2 .将第一步计算的结果与1相加
00000101 1=1，在这种情况下，表示该数字不存在，返回true
存储数据:删除数据的操作与保存数据的操作相同，唯一的区别是将对应的位位置设置为0。 可以通过首先将1向左移动以获得bitIdx位，然后将其反向，将结果与原始数据相加
例如，假设bitIdx=5，则数据为10110011
1.1左移5位后，取反011111
2 .将第一步计算的结果和数据相加
10110011 011111=10010011，删除成功
查找数据
关于class BitMap{public://位图的内存大小和数据范围的bitmap(size_trange ) 3360_bit(range/32 ) }voidset (语音)一致性//计算num在相应下标整数中的下标位置int bitIdx=num % 32； //将对应的位位置设置为1_bit[idx] |=1 bitIdx； }boolfind(constsize_tnum ) {int idx=num/32； int bitIdx=num % 32； 返回(bit [ idx ] bit idx ) 1； }voidreset(constsize_tnum ) {int idx=num/32； int bitIdx=num % 32； _bit[idx]=~(1bitidx )； }private:vectorint _bit； (； 测试截图：