題目：統(tǒng)計(jì)給定數(shù)字中浓镜，值為1的二進(jìn)制位的數(shù)量。如果是數(shù)組呢面殖？
解法1：遍歷算法
int getBitCount(unsigned int num) {
int count = 0;
while(num) {
if(num & 0x01)
count++;
num = num >> 1;
}
return count;
}
第一種想法比較簡單竖哩，從最后一位開始，比較是否為1脊僚，如果為1相叁，就計(jì)數(shù)器加一。循環(huán)次數(shù)固定辽幌，32次增淹。但是這種方法有一個(gè)地方需要注意，那就形參必須為unsigned int乌企。否則虑润，如果num為負(fù)數(shù)時(shí)，此時(shí)右移為了保證移位后還是負(fù)數(shù)加酵，最高位會(huì)一直置為1拳喻，那將陷入死循環(huán)哭当。
解法2：遍歷算法（改進(jìn)）
int getBitCount2(unsigned int num) {
int count = 0;
while(num) {
count++;
num = num & (num - 1);
}
return count;
}
相比較第一種算法，我們不必每次判斷一位冗澈，而是通過num & （num-1）來判斷钦勘。每次&之后，可以把num最低位的1置為0亚亲，那么循環(huán)的次數(shù)彻采，也就降低到了所含1的個(gè)數(shù)。
解法3：查表法
static const unsigned char bitsinbyte[256] = {
//0000 0000 - 0000 0001
0,1,
//0000 0010 - 0000 0011
1,2,
//0000 0100 - 0000 0111
1,2,2,3,
//0000 1000 - 0000 1111
1,2,2,3,2,3,3,4,
//0001 0000 - 0001 1111
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
//0010 0000 - 0011 1111
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,
//0100 0000 - 0111 1111
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,
//1000 0000 - 1111 1111
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
};
int getBitCount3(unsigned int num) {
unsigned char n1 = num;
unsigned char n2 = num >> 8;
unsigned char n3 = num >> 16;
unsigned char n4 = num >> 24;
return bitsinbyte[n1] + bitsinbyte[n2] +
bitsinbyte[n3] + bitsinbyte[n4];
}
通過定義一個(gè)bitsinbyte[256]字節(jié)數(shù)組捌归，里面存放0000 0000 - 1111 1111不同數(shù)字的1的個(gè)數(shù)肛响。然后把需要統(tǒng)計(jì)的數(shù)字劃分為四段，然后分部計(jì)算惜索。
解法4：variable-precision SWAR算法
unsigned int getBitCount4(unsigned int num) {
num = (num & 0x55555555) + ((num >> 1) & 0x55555555);
num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
num = (num & 0x0F0F0F0F) + ((num >> 4) & 0x0F0F0F0F);
num = (num * 0x01010101 >> 24);
return num;
}
這種算法也常被稱為漢明重量（Hamming Weight）特笋，通過一系列的位移和位運(yùn)算操作，可以在常數(shù)時(shí)間內(nèi)計(jì)算多個(gè)字節(jié)的漢明重量巾兆，而且不需要使用額外的內(nèi)存雹有。接下來分析以下這個(gè)算法。
為了方便描述臼寄，我們假定一個(gè)字節(jié)0xD8 ->(二進(jìn)制) 0B11011000從后往前，依次為1到8位溜宽，第一位為0吉拳，第八位為1。
step1：首先我們可以很容易的知道适揉，
0x55555555對應(yīng)的二進(jìn)制的數(shù)為0B 01010101 01010101 01010101 01010101留攒，而第一步運(yùn)算相當(dāng)于，把num奇偶位的數(shù)字進(jìn)行相加嫉嘀。并且存放在了奇數(shù)位炼邀，相加如有進(jìn)位則放在偶數(shù)位。step2：
0x33333333對應(yīng)的二進(jìn)制的數(shù)為0B 00110011 00110011 00110011 00110011剪侮，把num的奇數(shù)位拭宁，與下一個(gè)奇數(shù)位相加（第一位加第三位，第五位加第七位）瓣俯，把num的偶數(shù)位杰标，與下一個(gè)偶數(shù)位相加（第二位加第四位，第六位加第八位）彩匕。如有進(jìn)位腔剂，則保存到第三位，或者第七位驼仪。step3：
0x0F0F0F0F對應(yīng)的二進(jìn)制的數(shù)為0B 00001111 00001111 00001111 00001111掸犬，把num的每個(gè)字節(jié)中袜漩，前四位，與后四位相加湾碎。此時(shí)宙攻，每個(gè)字節(jié)中所含1的個(gè)數(shù)，都集中到了前四位胜茧。此時(shí)可以用0x0m0n0i0j來表示這個(gè)數(shù)粘优，其中m，n呻顽，i雹顺，j代表之前num每個(gè)字節(jié)所含1的個(gè)數(shù)。step4：也是最神奇的一步廊遍，通過這一步嬉愧，把m，n喉前，i没酣，j這四個(gè)數(shù)相加。得到最終的個(gè)數(shù)卵迂。在這一步裕便，我們不需要把
0x01010101化為二進(jìn)制。而是直接帶入運(yùn)算见咒。通過下面的計(jì)算式偿衰，我們可以看出相乘，然后右移24位改览，剛好就是我們所要的結(jié)果下翎。神奇~
運(yùn)算速度
|算法(ms)/數(shù)據(jù)級(jí)別| 10| 10^2| 10^3| 10^4| 10^5| 10^6| 10^7| 10^8|
| :----:| :----: | :----: | :----: | :----: | :----: | :----: | :----: |
|遍歷|0 |0 |1 |2 |26| 255 |2700 |29447|
|遍歷（改進(jìn)）|0 |0 |0 |1 |7 |74 |739 |8046|
|查表|0 |0 |0 |0 |2 |21 |202 |2166|
|SWAR|0 |0 |0 |0 |2 |19 |190 |1876|
以上是模擬不同的數(shù)據(jù)級(jí)別，運(yùn)行測試的結(jié)果宝当。
參考資料：
- http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer
- <<劍指offer>> 第十題
- <<redis設(shè)計(jì)與實(shí)現(xiàn)>> 第22章视事，BITCOUNT實(shí)現(xiàn)
- 測試代碼
