題目:統(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)
- 測試代碼