setbit,getbit這些命令在redis是如何儲存和獲取的呢？直接通過get獲取到的值我們?nèi)绾闻袛鄬?yīng)的位是0或者1？
在Redis中setbit,set,getbit,get這些命令本身都是對字符串(SDS)的操作。
當我們執(zhí)行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 |
執(zhí)行g(shù)etbit 16，對應(yīng)的byte為floor(16 / 8)，bit為16%8，我們可以立刻得到對應(yīng)的值為1，因為getbit為常數(shù)級計算，所以算法復(fù)雜度為O(1)
上篇文章中提到bitcount命令的參數(shù)start,end指的是byte而不是bit，所以我們?nèi)绻霚蚀_計算某bit位到bit位中1的數(shù)量，需要通過get命令將整個值取出來自己計算，下面我用PHP演示如何計算正確的結(jié)果(其實這種密集運算不適合PHP搞，但思路相同)
計算方法一：一個位一個位算(腦子不如高斯，我們一個一個加！)
connect(‘127.0.0.1’);$cacheKey = ‘bitmap’;//我們將7,8,10對應(yīng)的位置設(shè)置為1$redis->setBit($cacheKey, 7, 1);$redis->setBit($cacheKey, 8, 1);$redis->setBit($cacheKey, 10, 1);$value = $redis->get($cacheKey);/*** 解包(redis返回來的是二進制字符串，我們需要把它解成對應(yīng)的數(shù)字)* 關(guān)于unpack的用法，如果不了解，大家可以網(wǎng)上搜索學習，改天可以單獨寫篇文章分享*/$bitmap = unpack(‘C*’, $value); $count = 0; foreach($bitmap as $key => $number) { for($i = 0; $i > $i & 1) == 1) { $count++; } }}
看完之后有的同學會有疑問，代碼中($number >> $i & 1) == 1是怎么回事兒？
先不管>>，當一個數(shù)與1做與運算會發(fā)生什么？1的二進制表示為00000001，所以當與1做與運算后，如果結(jié)果為1(00000001)，說明這個數(shù)的最后一位肯定為1，反之為0，而>>右移位可以幫我們將計算好的最后一位扔掉。網(wǎng)上看到一種更簡潔的寫法：
$count = 0;foreach($bitmap as $key => $number) { //主要看這一段哈，更簡潔，更有通用性 while($number) { $count += $number & 1; $n >>= 1; }}
然而天外有天，人外有人，又發(fā)現(xiàn)一個更厲害的，上面的算法循環(huán)次數(shù)等于總位數(shù)，而下面這個做到了只循環(huán)包含1的位數(shù)的循環(huán)次數(shù)
$count = 0;foreach($bitmap as $key => $number) { //原理是什么？且聽我下面慢慢道來 while($number) { $number &= ($number – 1); $count++; }}
上面關(guān)鍵代碼只有一句$number &= ($number – 1);,上一個算法是一位一位的移除，這個算法是每次清除最右邊的1，因為二進制相加逢二進一，二進制數(shù)每加一，尾數(shù)就會從0變成1或者從1變成0，而每減一最后一位的1一定會變成0，這樣當我們計算$number & ($number-1)的時候，會將最右的1移除掉，比如9&8=1001&1000=1000,再比如8&7=1000&0111=0000。
上面的方法有一個最大的不確定因素就是其中1的個數(shù)，如果所有的位都為1，那么我們一次循環(huán)都節(jié)省不了(1MB的數(shù)據(jù)需要循環(huán)計算1_1024_1024*8=8388608,800多W次啊，你說CPU累不累？)
計算方法二：查表法
查表法是一種典型的空間換時間的算法，使用方法如下：
我們事前將一個字節(jié)(8位)對應(yīng)的1的個數(shù)計算出來，放到一個數(shù)組中
//對效率要求這么高，我們請出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對應(yīng)的位數(shù)為:{$map[125]}” . PHP_EOL;echo “67對應(yīng)的位數(shù)為:{$map[67]}” . PHP_EOL;
我在本地測試，通過查表法處理8MB的數(shù)據(jù)只需要0.7秒，而上面的方法需要2.3秒。當然上面的是8bit的表，如果改成16bit的表，速度會更快(但是空間占用會變大，根據(jù)實際情況調(diào)整)
計算方法三：variable-precision SWAR(不知道如何翻譯)
這是一個不會帶來內(nèi)存壓力并且效率還可以的算法
//這個最大支持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設(shè)置為一個比較小的數(shù)，方便理解，假設(shè)$n=153(0b10011001)
第一行：
($n&0x55555555的目的是以二個位為一個分組，取出后一位)
0b10011001 & 0b01010101 = 0b00010001(獲取奇數(shù)位)
0b01001100 & 0b01010101 = 0b01000100(因為向右移動了一位，so獲取偶數(shù)位)
0b00010001 + 0b01000100 = 0b01010101(結(jié)果中沒兩位表示其中1的個數(shù))
第二行、第三行。。。到最后一直都是一個思想，就是2合1，4合1，8合1，16合1,如果要計算64位，繼續(xù)32合1就可以了。
上面的PHP都是一個字節(jié)一個字節(jié)計算的，我們知道32位的數(shù)，占用4個字節(jié)，在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的數(shù)據(jù)量$value = $redis->get($cacheKey);//解壓，這里的N很重要(unsigned long (always 32 bit, big endian byte order))，因為redis里面的數(shù)據(jù)就是按大頭存的$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;
本機測試：
因為數(shù)據(jù)較大，我對2秒多的計算時間略滿意，Redis本身的bitcount會根據(jù)字符串長度自動選擇variable-precision SWAR還是查表法。
