問(wèn)題描述

任意給定一個(gè)32位無(wú)符號(hào)整數(shù)n，求n的二進(jìn)制表示中1的個(gè)數(shù)，比如n = 5（0101）時(shí)，返回2，n =?15（1111）時(shí)，返回4

這也是一道比較經(jīng)典的題目了，相信不少人面試的時(shí)候可能遇到過(guò)這道題吧，下面介紹了幾種方法來(lái)實(shí)現(xiàn)這道題，相信很多人可能見過(guò)下面的算法，但我相信很少有人見到本文中所有的算法。如果您上頭上有更好的算法，或者本文沒有提到的算法，請(qǐng)不要吝惜您的代碼，分享的時(shí)候，也是學(xué)習(xí)和交流的時(shí)候。

普通法

我總是習(xí)慣叫普通法，因?yàn)槲覍?shí)在找不到一個(gè)合適的名字來(lái)描述它，其實(shí)就是最簡(jiǎn)單的方法，有點(diǎn)程序基礎(chǔ)的人都能想得到，那就是移位+計(jì)數(shù)，很簡(jiǎn)單，不多說(shuō)了，直接上代碼，這種方法的運(yùn)算次數(shù)與輸入n最高位1的位置有關(guān)，最多循環(huán)32次。

int?BitCount(unsigned?int?n)
{
????unsigned?int?c?=0?;?//?計(jì)數(shù)器
????while?(n?>0)
????{
????????if((n?&1)?==1)?//?當(dāng)前位是1
????????????++c?;?//?計(jì)數(shù)器加1
????????n?>>=1?;?//?移位
????}
????return?c?;
}

一個(gè)更精簡(jiǎn)的版本如下

int?BitCount1(unsigned?int?n)
{
????unsigned?int?c?=0?;?//?計(jì)數(shù)器
????for?(c?=0;?n;?n?>>=1)?//?循環(huán)移位
????????c?+=?n?&1?;?//?如果當(dāng)前位是1，則計(jì)數(shù)器加1
????return?c?;
}

問(wèn)：如果輸入?yún)?shù)是int，這種方法還能奏效嗎？

如何修改？看看下面的方法：

int?BitCount(int?n)
{
????int?num?=?0;
????unsigned?int?flag?=?1;
????while(0?!=?flag)
????{
????????if(n?&?flag)
????????????num++;
????????flag?=?flag?<1;
????}
????return?num;
}

快速法

這種方法速度比較快，其運(yùn)算次數(shù)與輸入n的大小無(wú)關(guān)，只與n中1的個(gè)數(shù)有關(guān)。如果n的二進(jìn)制表示中有k個(gè)1，那么這個(gè)方法只需要循環(huán)k次即可。其原理是不斷清除n的二進(jìn)制表示中最右邊的1，同時(shí)累加計(jì)數(shù)器，直至n為0，代碼如下

int?BitCount2(unsigned?int?n)
{
????unsigned?int?c?=0?;
????for?(c?=0;?n;?++c)
????{
????????n?&=?(n?-1)?;?//?清除最低位的1
????}
????return?c?;
}

為什么n &= (n – 1)能清除最右邊的1呢？因?yàn)閺亩M(jìn)制的角度講，n相當(dāng)于在n - 1的最低位加上1。舉個(gè)例子，8（1000）= 7（0111）+ 1（0001），所以8 & 7 = （1000）&（0111）=?0（0000），清除了8最右邊的1（其實(shí)就是最高位的1，因?yàn)?的二進(jìn)制中只有一個(gè)1）。再比如7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），清除了7的二進(jìn)制表示中最右邊的1（也就是最低位的1）。

查表法

動(dòng)態(tài)建表

由于表示在程序運(yùn)行時(shí)動(dòng)態(tài)創(chuàng)建的，所以速度上肯定會(huì)慢一些，把這個(gè)版本放在這里，有兩個(gè)原因

1. 介紹填表的方法，因?yàn)檫@個(gè)方法的確很巧妙。

2. 類型轉(zhuǎn)換，這里不能使用傳統(tǒng)的強(qiáng)制轉(zhuǎn)換，而是先取地址再轉(zhuǎn)換成對(duì)應(yīng)的指針類型。也是常用的類型轉(zhuǎn)換方法。

int?BitCount3(unsigned?int?n)?
{?
????//?建表
????unsigned?char?BitsSetTable256[256]?=?{0}?;?

????//?初始化表?
????for?(int?i?=0;?i?<256;?i++)?
????{?
????????BitsSetTable256[i]?=?(i?&1)?+?BitsSetTable256[i?/2];?
????}?

????unsigned?int?c?=0?;?

????//?查表
????unsigned?char*?p?=?(unsigned?char*)?&n?;?

????c?=?BitsSetTable256[p[0]]?+?
????????BitsSetTable256[p[1]]?+?
????????BitsSetTable256[p[2]]?+?
????????BitsSetTable256[p[3]];?

????return?c?;?
}

先說(shuō)一下填表的原理，根據(jù)奇偶性來(lái)分析，對(duì)于任意一個(gè)正整數(shù)n

1.如果它是偶數(shù)，那么n的二進(jìn)制中1的個(gè)數(shù)與n/2中1的個(gè)數(shù)是相同的，比如4和2的二進(jìn)制中都有一個(gè)1，6和3的二進(jìn)制中都有兩個(gè)1。為啥？因?yàn)閚是由n/2左移一位而來(lái)，而移位并不會(huì)增加1的個(gè)數(shù)。

2.如果n是奇數(shù)，那么n的二進(jìn)制中1的個(gè)數(shù)是n/2中1的個(gè)數(shù)+1，比如7的二進(jìn)制中有三個(gè)1，7/2 = 3的二進(jìn)制中有兩個(gè)1。為啥？因?yàn)楫?dāng)n是奇數(shù)時(shí)，n相當(dāng)于n/2左移一位再加1。

再說(shuō)一下查表的原理

對(duì)于任意一個(gè)32位無(wú)符號(hào)整數(shù)，將其分割為4部分，每部分8bit，對(duì)于這四個(gè)部分分別求出1的個(gè)數(shù)，再累加起來(lái)即可。而8bit對(duì)應(yīng)2^8 = 256種01組合方式，這也是為什么表的大小為256的原因。

注意類型轉(zhuǎn)換的時(shí)候，先取到n的地址，然后轉(zhuǎn)換為unsigned char*，這樣一個(gè)unsigned int（4 bytes）對(duì)應(yīng)四個(gè)unsigned char（1 bytes），分別取出來(lái)計(jì)算即可。舉個(gè)例子吧，以87654321（十六進(jìn)制）為例，先寫成二進(jìn)制形式-8bit一組，共四組，以不同顏色區(qū)分，這四組中1的個(gè)數(shù)分別為4，4，3，2，所以一共是13個(gè)1，如下面所示。

10000111 01100101 01000011 00100001 = 4 + 4 + 3 + 2 = 13

靜態(tài)表-4bit

原理和8-bit表相同，詳見8-bit表的解釋

int?BitCount4(unsigned?int?n)
{
????unsigned?int?table[16]?=?
????{
????????0,?1,?1,?2,?
????????1,?2,?2,?3,?
????????1,?2,?2,?3,?
????????2,?3,?3,?4
????}?;

????unsigned?int?count?=0?;
????while?(n)
????{
????????count?+=?table[n?&0xf]?;
????????n?>>=4?;
????}
????return?count?;
}

靜態(tài)表-8bit

首先構(gòu)造一個(gè)包含256個(gè)元素的表table，table[i]即i中1的個(gè)數(shù)，這里的i是[0-255]之間任意一個(gè)值。然后對(duì)于任意一個(gè)32bit無(wú)符號(hào)整數(shù)n，我們將其拆分成四個(gè)8bit，然后分別求出每個(gè)8bit中1的個(gè)數(shù)，再累加求和即可，這里用移位的方法，每次右移8位，并與0xff相與，取得最低位的8bit，累加后繼續(xù)移位，如此往復(fù)，直到n為0。所以對(duì)于任意一個(gè)32位整數(shù)，需要查表4次。以十進(jìn)制數(shù)2882400018為例，其對(duì)應(yīng)的二進(jìn)制數(shù)為10101011110011011110111100010010，對(duì)應(yīng)的四次查表過(guò)程如下：紅色表示當(dāng)前8bit，綠色表示右移后高位補(bǔ)零。

第一次（n & 0xff） ? ? ? ? ?10101011110011011110111100010010

第二次（(n >> 8) & 0xff） ?00000000101010111100110111101111

第三次（(n >> 16) & 0xff）00000000000000001010101111001101

第四次（(n >> 24) & 0xff）00000000000000000000000010101011

int?BitCount7(unsigned?int?n)
{?
????unsigned?int?table[256]?=?
????{?
????????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,?
????};?

????return?table[n?&0xff]?+
????????table[(n?>>8)?&0xff]?+
????????table[(n?>>16)?&0xff]?+
????????table[(n?>>24)?&0xff]?;
}

當(dāng)然也可以搞一個(gè)16bit的表，或者更極端一點(diǎn)32bit的表，速度將會(huì)更快。

平行算法

網(wǎng)上都這么叫，我也這么叫吧，不過(guò)話說(shuō)回來(lái)，的確有平行的意味在里面，先看代碼，稍后解釋

int?BitCount4(unsigned?int?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)?;?
????n?=?(n?&0x0000ffff)?+?((n?>>16)?&0x0000ffff)?;?

????return?n?;?
}

速度不一定最快，但是想法絕對(duì)巧妙。說(shuō)一下其中奧妙，其實(shí)很簡(jiǎn)單，先將n寫成二進(jìn)制形式，然后相鄰位相加，重復(fù)這個(gè)過(guò)程，直到只剩下一位。

以217（11011001）為例，有圖有真相，下面的圖足以說(shuō)明一切了。217的二進(jìn)制表示中有5個(gè)1

完美法

int?BitCount5(unsigned?int?n)?
{
????unsigned?int?tmp?=?n?-?((n?>>1)?&033333333333)?-?((n?>>2)?&011111111111);
????return?((tmp?+?(tmp?>>3))?&030707070707)?%63;
}

最喜歡這個(gè)，代碼太簡(jiǎn)潔啦，只是有個(gè)取模運(yùn)算，可能速度上慢一些。區(qū)區(qū)兩行代碼，就能計(jì)算出1的個(gè)數(shù)，到底有何奧妙呢？為了解釋的清楚一點(diǎn)，我盡量多說(shuō)幾句。

第一行代碼的作用

先說(shuō)明一點(diǎn)，以0開頭的是8進(jìn)制數(shù)，以0x開頭的是十六進(jìn)制數(shù)，上面代碼中使用了三個(gè)8進(jìn)制數(shù)。

將n的二進(jìn)制表示寫出來(lái)，然后每3bit分成一組，求出每一組中1的個(gè)數(shù)，再表示成二進(jìn)制的形式。比如n = 50，其二進(jìn)制表示為110010，分組后是110和010，這兩組中1的個(gè)數(shù)本別是2和3。2對(duì)應(yīng)010，3對(duì)應(yīng)011，所以第一行代碼結(jié)束后，tmp = 010011，具體是怎么實(shí)現(xiàn)的呢？由于每組3bit，所以這3bit對(duì)應(yīng)的十進(jìn)制數(shù)都能表示為2^2 * a + 2^1 * b + c的形式，也就是4a + 2b + c的形式，這里a,b,c的值為0或1，如果為0表示對(duì)應(yīng)的二進(jìn)制位上是0，如果為1表示對(duì)應(yīng)的二進(jìn)制位上是1，所以a + b + c的值也就是4a + 2b + c的二進(jìn)制數(shù)中1的個(gè)數(shù)了。舉個(gè)例子，十進(jìn)制數(shù)6（0110）= 4 * 1 + 2 * 1 + 0，這里a = 1, b = 1, c = 0, a + b + c = 2，所以6的二進(jìn)制表示中有兩個(gè)1?，F(xiàn)在的問(wèn)題是，如何得到a + b + c呢？注意位運(yùn)算中，右移一位相當(dāng)于除2，就利用這個(gè)性質(zhì)！

4a + 2b + c 右移一位等于2a + b

4a + 2b + c 右移量位等于a

然后做減法

4a + 2b + c –(2a + b) – a = a + b + c，這就是第一行代碼所作的事，明白了吧。

第二行代碼的作用

在第一行的基礎(chǔ)上，將tmp中相鄰的兩組中1的個(gè)數(shù)累加，由于累加到過(guò)程中有些組被重復(fù)加了一次，所以要舍棄這些多加的部分，這就是&030707070707的作用，又由于最終結(jié)果可能大于63，所以要取模。

需要注意的是，經(jīng)過(guò)第一行代碼后，從右側(cè)起，每相鄰的3bit只有四種可能，即000, 001, 010, 011，為啥呢？因?yàn)槊?bit中1的個(gè)數(shù)最多為3。所以下面的加法中不存在進(jìn)位的問(wèn)題，因?yàn)? + 3 = 6，不足8，不會(huì)產(chǎn)生進(jìn)位。

tmp + (tmp >> 3)-這句就是是相鄰組相加，注意會(huì)產(chǎn)生重復(fù)相加的部分，比如tmp = 659 = 001 010 010 011時(shí)，tmp >> 3 = 000 001 010 010，相加得

001 010 010 011

000 001 010 010

001 011 100 101

011 + 101 = 3 + 5 = 8。（感謝網(wǎng)友Di哈指正。）注意，659只是個(gè)中間變量，這個(gè)結(jié)果不代表659這個(gè)數(shù)的二進(jìn)制形式中有8個(gè)1。

注意我們想要的只是第二組和最后一組（綠色部分），而第一組和第三組（紅色部分）屬于重復(fù)相加的部分，要消除掉，這就是&030707070707所完成的任務(wù)（每隔三位刪除三位），最后為什么還要%63呢？因?yàn)樯厦嫦喈?dāng)于每次計(jì)算相連的6bit中1的個(gè)數(shù)，最多是111111 = 77（八進(jìn)制）= 63（十進(jìn)制），所以最后要對(duì)63取模。

位標(biāo)志法

感謝網(wǎng)友 @gussing提供

struct?_byte?
{?
????unsigned?a:1;?
????unsigned?b:1;?
????unsigned?c:1;?
????unsigned?d:1;?
????unsigned?e:1;?
????unsigned?f:1;?
????unsigned?g:1;?
????unsigned?h:1;?
};?

long?get_bit_count(?unsigned?char?b?)?
{
????struct?_byte?*by?=?(struct?_byte*)&b;?
????return?(by->a+by->b+by->c+by->d+by->e+by->f+by->g+by->h);?
}

來(lái)源：https://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html