位图实现：在位图中采用比特位表示对应的元素存在或者不存在0：不存在 1：存在，例如一个int整数有32个比特位可以表示0-31个整数。
实现代码
 
class BitMap
{
public:
    BitMap(int size = 100)//size表示你需要表示元素的个数
    {
        _map.resize((size >> 5) + 1);//一个int可以表示32个元素，size个元素需要size/32 + 1个int来存储
        //注意+1因为1/32 = 0，但是我们需要一个int
    }
    void set(int num)//将标志位设置为1表示元素存在
    {
        int bite = num >> 5;//相当于/32//找出元素在数组中对应的下标
        int bit = num % 32;//找出元素对应的bit位
        _map[bite] |= (1 << bit);
    }
    void reset(int num)//将已存在元素删除，将对应的标志位置0
    {
        int bite = num >> 5;//相当于/32//找出元素在数组中对应的下标
        int bit = num % 32;//找出元素对应的bit位
        _map[bite] &= ~(1 << bit);
    }
    bool test(int num)
    {
        int bite = num >> 5;//相当于/32//找出元素在数组中对应的下标
        int bit = num % 32;//找出元素对应的bit位
        if (_map[bite] & (1 << bit))
            return true;
        else
            return false;
    }
private:
    vector<int> _map;
};
int main()
{
    BitMap _map(1024);
    _map.set(1);
    bool ret = _map.test(1);
    _map.reset(1);
    ret = _map.test(1);
    _map.set(33);
    ret = _map.test(33);
    _map.reset(33);
    ret = _map.test(33);

    _map.set(555);
    ret = _map.test(555);
    ret = _map.test(100);

}
 
位图优点：速度快，内存空间占用小，能表示大范围数据
位图的缺点 
 1.可读性差 
 2.存储元素的个数比一般元素要多，但是存储元素的大小受空间大小的限制。
位图的应用 
 1）给定100亿个整数，设计算法找到只出现一次的整数 
 100亿个整数采用位图存储的话需要1.5G的内存，并且如果需要记录出现次数的话一个比特位 
 是无法做到的，我们需要2个比特位那么就需要2.5G的内存，如果我们系统的内存不足够的话， 
 我们需要将100亿个数据分成1000份文件，将每个文件的数据通过位图存储，我们采用两个比特位 
 00：没有出现，01，出现一次，10出现多次，11舍弃，再将这1000个文件中出现一次的数据， 
 统计到一个文件里 
 2）给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集 
 将第一个文件的数据分成1000份存储到位图里，再判断第二份文件中的数据是否在位图中。 
 3）1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数 
 我们需要将100亿个数据分成1000份文件，将每个文件的数据通过位图存储，我们采用两个比特位 
 00：没有出现，01，出现一次，10出现2次，11舍弃，再将这1000个文件中出现不超过两次次的数据

上课签到时间到了，张三老师开始点名了，每点一名同学就新增加一条记录，我们数据库会把这条记录写到学生考勤表里，到学期末考核的时候汇总根据学生迟到次数计算总学分。假设一个班级50个学生，一天4课时，一个星期就要记录1000条记录，那么如果说我们根据学生的学号顺序记录学生签到信息，通过“0”和“1”来表示，“1”就代表学生签到，“0”代表学生迟到，那么我们一个星期只要保存20条数据即可。
 
Redis也有这样的结构名叫位图，位图最小的单位是bit，每个bit是由0或1构成，我们的字符串就是由很多个bit数组组成的，所以我们在使用位图的时候是可以把一组bit转换成字符串，也可以由字符串转换成bit数组。
 
位图基本用法
 
如下，“h”的ACSLL码是0110 1000
 
> setbit name 1 1    #设置位图的位置(integer) 0> setbit name 2 1(integer) 0> setbit name 4 1(integer) 0> get name          #获取这个位图转换成字符串的值"h"> getbit name 1     #获取位图的某个位置是否有值(integer) 1> getbit name 3(integer) 0
 
字符串转位图
 
> set kh h       #存字符串OK> getbit kh 1    #第二个位置的bit是1(integer) 1> getbit kh 3    #第四个位置的bit是0(integer) 0
 
注意：如果对应位的字节是不可打印字符，redis会显示该字符的十六进制形式。
 
> setbit x O 1(integer) 0> setbit x 1 1(integer) 0> get x"＼xc0"
 
统计和查找
 
Redis位图提供bitcount和bitpos指令，bitcount用来统计一定范围内1的个数，bitpos用来查找指定范围内出现的第一个0或者1。
 
这里我们需要注意的是参数start_index和end_index是字节索引，简单的来说就是他们只能是8的倍数而不是指定值。
 
咱们对照下图来看
 
 
> set name helloOK127.0.0.1:6379> bitcount name    #计数所有的1的个数(integer) 21127.0.0.1:6379> bitcount name 0 1    #获取前两个字符出现1的个数(integer) 7127.0.0.1:6379> bitcount name 0 0    #获取第一个字符出现1的个数(integer) 3127.0.0.1:6379> bitpos name 1    #获取第一个1出现的位置(integer) 1127.0.0.1:6379> bitpos name 0    #获取第一个0出现的位置(integer) 0127.0.0.1:6379> bitpos name 1 1 1    #获取第二个字符1出现的位置(integer) 9
 
关于位图批量操作
 
我们通过setbit和getbit指令来操作位图都是一次操作一个位，那么有时候我们需要一次性操作多个位，如何操作呢？
 
在Redis3.2版本之前我们可以使用管道来一次性操作多个指令，redis给我们提供了bitfield指令，该指令有三个子指令分别是get、set、incrby它们都可以对指定位片段进行读写，但是最多只能处理64个连续的位，如果超过64位，就得使用多个子指令，bitfield 可以一次执行多个子指令。
 
Get
 
下面我们来看例子，还是使用上面的name=hello
 
字母
数值
二进制
h
104
0110 1000
e
101
0110 0101
l
108
0110 1100
l
108
0110 1100
o
111
0110 1111
> bitfield name get u4 0    #第一个位开始取4个位(0110)，结果为无符号数(u)(integer) 6> bitfield name get u3 2    #第三个位开始取3个位(101)，结果为无符号数(u)(integer) 5> bitfield name get i4 0    #第一个位开始取4个位(0110)，结果为有符号数(i)(integer) 6> bitfield name get i3 2    #第三个位开始取3个位(101)，结果为有符号数(i)(integer) -3
 
下面我们才试试批处理
 
> bitfield name get u4 0 get u3 2 get i4 0 get i3 2(integer) 6(integer) 5(integer) 6(integer) -3
 
有符号数是指获取的位数组中第一个位是符号位，剩下的才是值。如果第一位是1，那就是负数。无符号数表示非负数，没有符号位，获取的位数组全部都是值。有符号数最多可以获取 64 位，无符号数只能获取 63 位（因为 Redis 协议中的integer是有符号数，最大 64 位，不能传递 64 位无符号值）。
 
Set
 
下面我们来使用set，把hello的e变成a，a的ASCLL码是97
 
>bitfield name set u8 8 97    #从第八位开始，接下来的8位用无符号的ASCLL码97代替(integer)101 >get name"hallo"
 
Incrby
 
这个指令用来自增，如果自增到最大值的时候会溢出，如果是无符号那么就变成0，如果是有符号的就会变成负数，向下自增反之。
 
bitfield指令提供溢出策略的指令overflow，用户可以指定类型，默认为：wrap，溢出及折返，还可以选择失败：fail，失败不执行，截断：sat，溢出就停留。
 
> bitfield name incrby u4 2 1    #从第三个位开始，对接下来的4位元符号数＋ 1(integer) 11> bitfield name incrby u4 2 1(integer) 12> bitfield name incrby u4 2 1(integer) 13> bitfield name incrby u4 2 1(integer) 14> bitfield name incrby u4 2 1(integer) 15####sat> bitfield name overflow sat incrby u4 2 1    #保持最大值(integer) 15####fail> bitfield name overflow fail incrby u4 2 1    #不执行(nil)####wrap> bitfield name incrby u4 2 1    #溢出折返(integer) 0
 
​
 
 
 
一名正在抢救的coder
 
笔名：mangolove
 
CSDN地址：https://blog.csdn.net/mango_love
 
GitHub地址：https://github.com/mangoloveYu