摘要：在中這些命令本身都是對(duì)字符串的操作。到最后一只都是一個(gè)思想，就是合，合，合，合如果要計(jì)算位，繼續(xù)合就可以了。

setbit,getbit這些命令在redis是如何儲(chǔ)存和獲取的呢？直接通過get獲取到的值我們?nèi)绾闻袛鄬?duì)應(yīng)的位是0或者1？

本編文章可以看為[Redis中BitMap的妙用]的續(xù)篇。

在Redis中setbit,set,getbit,get這些命令本身都是對(duì)字符串(SDS)的操作。

當(dāng)我們執(zhí)行setbit key (0,2,5,9,12,16,21) 1命令后，bitmap表示如下圖：

執(zhí)行getbit 16，對(duì)應(yīng)的byte為floor(16 / 8)，bit為16%8，我們可以立刻得到對(duì)應(yīng)的值為1，因?yàn)?b>getbit為常數(shù)級(jí)計(jì)算，所以算法復(fù)雜度為O(1)

上篇文章中提到bitcount命令的參數(shù)start,end指的是byte而不是bit，所以我們?nèi)绻霚?zhǔn)確計(jì)算某bit位到bit位中1的數(shù)量，需要通過get命令將整個(gè)值取出來自己計(jì)算，下面我用PHP演示如何計(jì)算正確的結(jié)果(其實(shí)這種密集運(yùn)算不適合PHP搞，但思路相同)

connect("127.0.0.1");

$cacheKey = "bitmap";
//我們將7,8,10對(duì)應(yīng)的位置設(shè)置為1
$redis->setBit($cacheKey, 7, 1);
$redis->setBit($cacheKey, 8, 1);
$redis->setBit($cacheKey, 10, 1);

$value = $redis->get($cacheKey);

/**
* 解包(redis返回來的是二進(jìn)制字符串，我們需要把它解成對(duì)應(yīng)的數(shù)字)
* 關(guān)于unpack的用法，如果不了解，大家可以網(wǎng)上搜索學(xué)習(xí)，改天可以多帶帶寫篇文章分享
*/
$bitmap = unpack("C*", $value);
    $count = 0;
    foreach($bitmap as $key => $number) {
    for($i = 0; $i < 8; $i++) {
        if(($number >> $i & 1) == 1) {
            $count++;
        }
    }
}

看完之后有的同學(xué)會(huì)有疑問，代碼中($number >> $i & 1) == 1是怎么回事兒？

先不管>>，當(dāng)一個(gè)數(shù)與1做與運(yùn)算會(huì)發(fā)生什么？1的二進(jìn)制表示為00000001，所以當(dāng)與1做與運(yùn)算后，如果結(jié)果為1(00000001)，說明這個(gè)數(shù)的最后一位肯定為1，反之為0，而>>右移位可以幫我們將計(jì)算好的最后一位扔掉。網(wǎng)上看到一種更簡(jiǎn)潔的寫法：

$count = 0;
foreach($bitmap as $key => $number) {
    //主要看這一段哈，更簡(jiǎn)潔，更有通用性
    while($number) {
        $count += $number & 1;
        $n >>= 1;
    }
}

然而天外有天，人外有人，又發(fā)現(xiàn)一個(gè)更厲害的，上面的算法循環(huán)次數(shù)等于總位數(shù)，而下面這個(gè)做到了只循環(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);,上一個(gè)算法是一位一位的移除，這個(gè)算法是每次清除最右邊的1，因?yàn)槎M(jìn)制相加逢二進(jìn)一，二進(jìn)制數(shù)每加一，尾數(shù)就會(huì)從0變成1或者從1變成0，而每減一最后一位的1一定會(huì)變成0，這樣當(dāng)我們計(jì)算$number & ($number-1)的時(shí)候，會(huì)將最右的1移除掉，比如9&8=1001&1000=1000,再比如8&7=1000&0111=0000。

上面的方法有一個(gè)最大的不確定因素就是其中1的個(gè)數(shù)，如果所有的位都為1，那么我們一次循環(huán)都節(jié)省不了(1MB的數(shù)據(jù)需要循環(huán)計(jì)算1_1024_1024*8=8388608,800多W次啊，你說CPU累不累？)

查表法是一種典型的空間換時(shí)間的算法，使用方法如下：

我們事前將一個(gè)字節(jié)(8位)對(duì)應(yīng)的1的個(gè)數(shù)計(jì)算出來，放到一個(gè)數(shù)組中

//對(duì)效率要求這么高，我們請(qǐng)出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對(duì)應(yīng)的位數(shù)為:{$map[125]}" . PHP_EOL;
echo "67對(duì)應(yīng)的位數(shù)為:{$map[67]}" . PHP_EOL;

我在本地測(cè)試，通過查表法處理8MB的數(shù)據(jù)只需要0.7秒，而上面的方法需要2.3秒。當(dāng)然上面的是8bit的表，如果改成16bit的表，速度會(huì)更快(但是空間占用會(huì)變大，根據(jù)實(shí)際情況調(diào)整)

這是一個(gè)不會(huì)帶來內(nèi)存壓力并且效率還可以的算法

//這個(gè)最大支持32位運(yùn)算
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開頭代表十六進(jìn)制0b開頭代表二進(jìn)制)

0x55555555=0b0101010101010101

0x33333333=0b0011001100110011

0x0f0f0f0f=0b0000111100000011

我們將$n設(shè)置為一個(gè)比較小的數(shù)，方便理解，假設(shè)$n=153(0b10011001)

第一行：

($n&0x55555555的目的是以二個(gè)位為一個(gè)分組，取出后一位)

0b10011001 & 0b01010101 = 0b00010001(獲取奇數(shù)位)

0b01001100 & 0b01010101 = 0b01000100(因?yàn)橄蛴乙苿?dòng)了一位，so獲取偶數(shù)位)

0b00010001 + 0b01000100 = 0b01010101(結(jié)果中沒兩位表示其中1的個(gè)數(shù))

第二行、第三行。。。到最后一只都是一個(gè)思想，就是2合1，4合1，8合1，16合1,如果要計(jì)算64位，繼續(xù)32合1就可以了。

上面的PHP都是一個(gè)字節(jié)一個(gè)字節(jié)計(jì)算的，我們知道32位的數(shù)，占用4個(gè)字節(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))，因?yàn)閞edis里面的數(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;

本機(jī)測(cè)試：

get數(shù)據(jù)花費(fèi)0.01s

unpack花費(fèi)0.9s

foreach+計(jì)算花費(fèi)1.48s

總花費(fèi)2.46s

因?yàn)閿?shù)據(jù)較大，我對(duì)2秒多的計(jì)算時(shí)間略滿意，Redis本身的bitcount會(huì)根據(jù)字符串長(zhǎng)度自動(dòng)選擇variable-precision SWAR還是查表法。

技術(shù)手段沒有什么最好，只有最合適。如果本文幫到了你，關(guān)注公眾號(hào)支持一下。