題目：統(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; }

第一種想法比較簡(jiǎn)單，從最后一位開(kāi)始，比較是否為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; }

相比較第一種算法，我們不必每次判斷一位，而是通過(guò)num & （num-1）來(lái)判斷。每次&之后，可以把num最低位的1置為0，那么循環(huán)的次數(shù)，也就降低到了所含1的個(gè)數(shù)。

解法3：查表法

static const unsigned char bitsinbyte[256] = {//0000 0000 - 0000 00010,1,//0000 0010 - 0000 00111,2,//0000 0100 - 0000 01111,2,2,3,//0000 1000 - 0000 11111,2,2,3,2,3,3,4,//0001 0000 - 0001 11111,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,//0010 0000 - 0011 11111,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 11111,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 11111,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]; }

通過(guò)定義一個(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; }

這種算法也常被稱(chēng)為漢明重量（Hamming Weight），通過(guò)一系列的位移和位運(yùn)算操作，可以在常數(shù)時(shí)間內(nèi)計(jì)算多個(gè)字節(jié)的漢明重量，而且不需要使用額外的內(nèi)存。接下來(lái)分析以下這個(gè)算法。

為了方便描述，我們假定一個(gè)字節(jié)0xD8 ->(二進(jìn)制) 0B11011000從后往前，依次為1到8位，第一位為0，第八位為1。

• step1：首先我們可以很容易的知道，0x55555555對(duì)應(yīng)的二進(jìn)制的數(shù)為0B 01010101 01010101 01010101 01010101，而第一步運(yùn)算相當(dāng)于，把num奇偶位的數(shù)字進(jìn)行相加。并且存放在了奇數(shù)位，相加如有進(jìn)位則放在偶數(shù)位。

• step2：0x33333333對(duì)應(yīng)的二進(jìn)制的數(shù)為0B 00110011 00110011 00110011 00110011，把num的奇數(shù)位，與下一個(gè)奇數(shù)位相加（第一位加第三位，第五位加第七位），把num的偶數(shù)位，與下一個(gè)偶數(shù)位相加（第二位加第四位，第六位加第八位）。如有進(jìn)位，則保存到第三位，或者第七位。

• step3：0x0F0F0F0F對(duì)應(yīng)的二進(jìn)制的數(shù)為0B 00001111 00001111 00001111 00001111，把num的每個(gè)字節(jié)中，前四位，與后四位相加。此時(shí)，每個(gè)字節(jié)中所含1的個(gè)數(shù)，都集中到了前四位。此時(shí)可以用0x0m0n0i0j來(lái)表示這個(gè)數(shù)，其中m，n，i，j代表之前num每個(gè)字節(jié)所含1的個(gè)數(shù)。

• step4：也是最神奇的一步，通過(guò)這一步，把m，n，i，j這四個(gè)數(shù)相加。得到最終的個(gè)數(shù)。在這一步，我們不需要把0x01010101化為二進(jìn)制。而是直接帶入運(yùn)算。通過(guò)下面的計(jì)算式，我們可以看出相乘，然后右移24位，剛好就是我們所要的結(jié)果。神奇~

magic.png

運(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)行測(cè)試的結(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)
• 測(cè)試代碼

from:?http://www.jianshu.com/p/34fd5d477826?hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io

總結(jié)

以上是生活随笔為你收集整理的一道简单的算法题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。