轉(zhuǎn)自：http://s.sousb.com/?p=253

編程之美2.1節(jié)中的擴(kuò)展題第1題：如果變量是32位的Dword，則如何統(tǒng)計(jì)該二進(jìn)制數(shù)中1的個(gè)數(shù)。

對(duì)于該題，原本的想法還是想采用書中解法三，也就是用統(tǒng)計(jì)1中個(gè)數(shù)的算法v&(v-1)，該算法時(shí)間復(fù)雜度為該32二進(jìn)制數(shù)中“1”的個(gè)數(shù)。后來(lái)，參見了書中鏈接里的解法，該解法甚妙，復(fù)雜度只有若干個(gè)位運(yùn)算，與“1”的數(shù)目無(wú)關(guān)。由于下面這段程序?qū)懙谋容^難懂，所以在這里解釋一下他的解法。

解法一：

view plaincopy to clipboardprint?

int?Count(unsigned?x)??

{??

???x?=?x?-?((x?>>?1)?&?0x55555555);??//?1??

???x?=?(x?&?0x33333333)?+?((x?>>?2)?&?0x33333333);???//?2??

???x?=?(x?+?(x?>>?4))?&?0x0F0F0F0F;????//3??

???x?=?x?+?(x?>>?8);???//4??

???x?=?x?+?(x?>>?16);???//5??

???return?x?&?0x0000003F;??//?6??

}??

我們以0000 0000 0000 0000 0000 0000 1011 0101為例：

第一行中，x>>1是右移一位，(x>>1) 為 0000 0000 0000 0000 0000 0000 0101 1010，該結(jié)果與0101 0101 0101 0101 0101 0101 0101 0101相與，等于 0000 0000 0000 0000 0000 0000 0101 0000，實(shí)際上，((x >> 1) & 0×55555555) 該步是想得到原數(shù)據(jù)x的偶數(shù)位的數(shù)據(jù)。（代碼是先右移，再得奇數(shù)位，這個(gè)等價(jià)于：先得偶數(shù)位，再右移）然后，x-((x >> 1) & 0×55555555) 則是 用原數(shù)據(jù)減去原數(shù)據(jù)的偶數(shù)位。結(jié)果是 0000 0000 0000 0000 0000 0000 0110 0101，其實(shí)，之所有要相減就是為了得到第一位與第二位1的個(gè)數(shù)的和，第三位與第四位1的個(gè)數(shù)的和，第五位與第六位1的個(gè)數(shù)的和，以此類推。那么，為什么要用相減的方法來(lái)得到相鄰兩位的和呢？原理是：相鄰兩位1的個(gè)數(shù)的和是：A-A/2 。原數(shù)據(jù)是A，右移相當(dāng)于除2。比如，如果原數(shù)據(jù)是1（01），那么一半就是0，相減后就是1，所以有1個(gè)“1”。如果原數(shù)據(jù)是3（11），那么一半就是1，相減后就是2，所有總共有2個(gè)“1”。這樣，經(jīng)過(guò)第一行的運(yùn)算，我們得到每?jī)蓚€(gè)相鄰位的“1”的總和。

第二行，類似的，是求將原數(shù)據(jù)第一位第二位的“1“的個(gè)數(shù)的和 與 第三位第四位的“1”的個(gè)數(shù)的和 相加。這樣，第二行執(zhí)行后，我們可以得到每四位的“1”的個(gè)數(shù)的和

第三行，可以得到每八位的“1”的個(gè)數(shù)的和

第四行，可以得到每16位“1”的個(gè)數(shù)的和

第五行，可以得到32位數(shù)中所有1的個(gè)數(shù)的和。

第六行，由于32位的數(shù)據(jù)，1的個(gè)數(shù)最大也就32個(gè)，不可能超過(guò)2的6位方，所以只要取最后6位數(shù)據(jù)就是所有數(shù)據(jù)1的個(gè)數(shù)的和了。

這里用的是二分法，兩兩一組相加，之后四個(gè)四個(gè)一組相加，接著八個(gè)八個(gè)，最后就得到各位之和了。

解法二：

view plaincopy to clipboardprint?

int?Count(unsigned?x)??

{??

???unsigned?n;??????

??

???n?=?(x?>>?1)?&?033333333333;???//?1??

???x?=?x?-?n;??//?2??

???n?=?(n?>>?1)?&?033333333333;??//?3??

???x?=?x?-?n;???//?4??

???x?=?(x?+?(x?>>?3))?&?030707070707;??//5??

???x?=?modu(x,?63);???//?6??

???return?x;??//7??

}??

這個(gè)解法更妙。需要注意的是，033333333333和033333333333都是指 八進(jìn)制的數(shù)。第一行第二行連起來(lái)看，這與解法一很類似，目的是為了得到第一位與第二位的“1”的個(gè)數(shù)和。注意，第31、32位中1的個(gè)數(shù)和在這一步中被統(tǒng)計(jì)好了。

第一行和第三行、第四行連起來(lái)看，目的是為了得到第一位與第三位的“1”的個(gè)數(shù)的和。然后，再與上步的結(jié)果加起來(lái)，就得到第一位、第二位、第三位的“1”的個(gè)數(shù)的和。所以，從第一行到第四行就是為了得到 每三位一組的“1”的個(gè)數(shù)的和。原理是：

相鄰三位的結(jié)果是：A-A/2-A/4. 算法中有兩次向移。比如，第一位第二位第三位是011, 則第一次移位后為01，相減后為10，再移位后為0，相減還是10，所以有2個(gè)“1”。再比如，第一位第二位第三位是101，則第一次移位后為10，相減后為011，再移位后為1，相減后是010，所以有2個(gè)“1”。第五行是求相鄰六位的1的個(gè)數(shù)第六行，比較難懂。在第五行執(zhí)行完后，我們得到了七組數(shù)據(jù)，第32、31位為一組，第30-25為一組，……第6-第1為一組。所以可以寫成:x_0 + x_1 * 64 + x_2 * 64 * 64 + x_3 * 64 * 64* 64+ x_4 * 64 * 64* 64* 64+ x_5 * 64 * 64* 64* 64* 64+ x_6 * 64 * 64* 64* 64* 64* 64，這個(gè)數(shù)除以63的余數(shù) 肯定 與 x_0 +……+x_6 相等（因?yàn)?2位的數(shù)據(jù)最多也就32個(gè)1）簡(jiǎn)短解釋：首先是將二進(jìn)制各位三個(gè)一組，求出每組中1的個(gè)數(shù)，然后相鄰兩組歸并，得到六個(gè)一組的1的個(gè)數(shù)，最后很巧妙的用除63取余得到了結(jié)果。

這個(gè)程序只需要十條左右指令，而且不訪存，速度很快。

總結(jié)

以上是生活随笔為你收集整理的编程之美求二进制数中1的个数扩展题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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