在Redis中setbit,set,getbit,get这些命令本身都是对字符串(SDS)的操作。
当我们实行setbit key (0,2,5,9,12,16,21) 1命令后，bitmap表示如下图：
byte
bit0
bit1
bit2
bit3
bit4
bit5
bit6
bit7
byte0
1
0
1
0
0
1
0
0
byte1
0
1
0
0
1
0
0
0
byte2
1
0
0
0
0
1
0
0
实行getbit 16，对应的byte为floor(16 / 8)，bit为16%8，我们可以急速得到对应的值为1，由于getbit为常数级打算，以是算法繁芜度为O(1)
上篇文章中提到bitcount命令的参数start,end指的是byte而不是bit，以是我们如果想准确打算某bit位到bit位中1的数量，须要通过get命令将全体值取出来自己打算，下面我用PHP演示如何打算精确的结果(实在这种密集运算不适宜PHP搞，但思路相同)
打算方法一：一个位一个位算(脑筋不如高斯，我们一个一个加！)
<?php$redis = new Redis();$redis->connect('127.0.0.1');$cacheKey = 'bitmap';//我们将7,8,10对应的位置设置为1$redis->setBit($cacheKey, 7, 1);$redis->setBit($cacheKey, 8, 1);$redis->setBit($cacheKey, 10, 1);$value = $redis->get($cacheKey);/ 解包(redis返回来的是二进制字符串，我们须要把它解成对应的数字) 关于unpack的用法，如果不理解，大家可以网上搜索学习，改天可以单独写篇文章分享/$bitmap = unpack('C', $value); $count = 0; foreach($bitmap as $key => $number) { for($i = 0; $i < 8; $i++) { if(($number >> $i & 1) == 1) { $count++; } }}
看完之后有的同学会有疑问，代码中($number >> $i & 1) == 1是怎么回事儿？
先不管>>，当一个数与1做与运算会发生什么？1的二进制表示为00000001，以是当与1做与运算后，如果结果为1(00000001)，解释这个数的末了一位肯定为1，反之为0，而>>右移位可以帮我们将打算好的末了一位扔掉。网上看到一种更简洁的写法：
$count = 0;foreach($bitmap as $key => $number) { //紧张看这一段哈，更简洁，更有通用性 while($number) { $count += $number & 1; $n >>= 1; }}
然而天外有天，人外有人，又创造一个更厉害的，上面的算法循环次数即是总位数，而下面这个做到了只循环包含1的位数的循环次数
$count = 0;foreach($bitmap as $key => $number) { //事理是什么？且听我下面逐步道来 while($number) { $number &= ($number - 1); $count++; }}
上面关键代码只有一句$number &= ($number - 1);,上一个算法是一位一位的移除，这个算法是每次打消最右边的1，由于二进制相加逢二进一，二进制数每加一，尾数就会从0变成1或者从1变成0，而每减一末了一位的1一定会变成0，这样当我们打算$number & ($number-1)的时候，会将最右的1移除掉，比如9&8=1001&1000=1000,再比如8&7=1000&0111=0000。
上面的方法有一个最大的不愿定成分便是个中1的个数，如果所有的位都为1，那么我们一次循环都节省不了(1MB的数据须要循环打算1_1024_10248=8388608,800多W次啊，你说CPU累不累？)
打算方法二：查表法查表法是一种范例的空间换韶光的算法，利用方法如下：
我们事前将一个字节(8位)对应的1的个数打算出来，放到一个数组中
//对效率哀求这么高，我们请出PHP的SplFixedArray$map = SplFixedArray::fromArray(array(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,));echo "125对应的位数为:{$map[125]}" . PHP_EOL;echo "67对应的位数为:{$map[67]}" . PHP_EOL;
我在本地测试，通过查表法处理8MB的数据只须要0.7秒，而上面的方法须要2.3秒。当然上面的是8bit的表，如果改成16bit的表，速率会更快(但是空间占用会变大，根据实际情形调度)
打算方法三：variable-precision SWAR(不知道如何翻译)这是一个不会带来内存压力并且效率还可以的算法
//这个最大支持32位运算function getCount($n) { $n = ($n & 0x55555555) + (($n >> 1) & 0x55555555); //line1 $n = ($n & 0x33333333) + (($n >> 2) & 0x33333333); //line2 $n = ($n & 0x0f0f0f0f) + (($n >> 4) & 0x0f0f0f0f); //line3 $n = ($n & 0x00ff00ff) + (($n >> 8) & 0x00ff00ff); //line4 $n = ($n & 0x0000ffff) + (($n >> 16) & 0x0000ffff); //line5 return $n;}
一眼看上去，这什么什么啊。。(0x开头代表十六进制0b开头代表二进制)
0x55555555=0b0101010101010101
0x33333333=0b0011001100110011
0x0f0f0f0f=0b0000111100000011
我们将$n设置为一个比较小的数，方便理解，假设$n=153(0b10011001)
第一行：
($n&0x55555555的目的因此二个位为一个分组，取出后一位)
0b10011001 & 0b01010101 = 0b00010001(获取奇数位)
0b01001100 & 0b01010101 = 0b01000100(由于向右移动了一位，so获取偶数位)
0b00010001 + 0b01000100 = 0b01010101(结果中没两位表示个中1的个数)
第二行、第三行。。。到末了一贯都是一个思想，便是2合1，4合1，8合1，16合1,如果要打算64位，连续32合1就可以了。
上面的PHP都是一个字节一个字节打算的，我们知道32位的数，占用4个字节，在PHP如何处理比较好呢
$redis = new Redis();$redis->connect('127.0.0.1');$cacheKey = 'bitmap'$redis->setBit($cacheKey, 1, 1);$redis->setBit($cacheKey, 12345, 1);$redis->setBit($cacheKey, 123456789, 1);//大约14MB的数据量$value = $redis->get($cacheKey);//解压，这里的N很主要(unsigned long (always 32 bit, big endian byte order))，由于redis里面的数据便是按大头存的$bitmap = unpack('N', $value);$total = 0;foreach($bitmap as $n) { $n = ($n & 0x55555555) + (($n >> 1) & 0x55555555); $n = ($n & 0x33333333) + (($n >> 2) & 0x33333333); $n = ($n & 0x0f0f0f0f) + (($n >> 4) & 0x0f0f0f0f); $n = ($n & 0x00ff00ff) + (($n >> 8) & 0x00ff00ff); $total += ($n & 0x0000ffff) + (($n >> 16) & 0x0000ffff);}echo $total;
本机测试：
get数据花费0.01sunpack花费0.9sforeach+打算花费1.48s总花费2.46s由于数据较大，我对2秒多的打算韶光略满意，Redis本身的bitcount会根据字符串长度自动选择variable-precision SWAR还是查表法。
