當(dāng)前位置:首頁 > 公眾號精選 > 21ic電子網(wǎng)
[導(dǎo)讀]作者:翰墨小生 鏈接:https://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html 問題描述 任意給定一個32位無符號整數(shù)n,求n的二進制表示中1的個數(shù),比如n = 5(0101)時,返回2,n = 15(1111)時,返回4 這也是一道比較經(jīng)典的題目了,相信不少人


作者:翰墨小生

鏈接:https://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html

問題描述

任意給定一個32位無符號整數(shù)n,求n的二進制表示中1的個數(shù),比如n = 5(0101)時,返回2,n = 15(1111)時,返回4

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

普通法

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

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

一個更精簡的版本如下

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

問:如果輸入?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;
}


快速法

這種方法速度比較快,其運算次數(shù)與輸入n的大小無關(guān),只與n中1的個數(shù)有關(guān)。如果n的二進制表示中有k個1,那么這個方法只需要循環(huán)k次即可。其原理是不斷清除n的二進制表示中最右邊的1,同時累加計數(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呢?因為從二進制的角度講,n相當(dāng)于在n - 1的最低位加上1。舉個例子,8(1000)= 7(0111)+ 1(0001),所以8 & 7 = (1000)&(0111)= 0(0000),清除了8最右邊的1(其實就是最高位的1,因為8的二進制中只有一個1)。再比如7(0111)= 6(0110)+ 1(0001),所以7 & 6 = (0111)&(0110)= 6(0110),清除了7的二進制表示中最右邊的1(也就是最低位的1)。

查表法

動態(tài)建表

由于表示在程序運行時動態(tài)創(chuàng)建的,所以速度上肯定會慢一些,把這個版本放在這里,有兩個原因

  1. 介紹填表的方法,因為這個方法的確很巧妙。

  2. 類型轉(zhuǎn)換,這里不能使用傳統(tǒng)的強制轉(zhuǎn)換,而是先取地址再轉(zhuǎn)換成對應(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 ; 
}

先說一下填表的原理,根據(jù)奇偶性來分析,對于任意一個正整數(shù)n

1.如果它是偶數(shù),那么n的二進制中1的個數(shù)與n/2中1的個數(shù)是相同的,比如4和2的二進制中都有一個1,6和3的二進制中都有兩個1。為啥?因為n是由n/2左移一位而來,而移位并不會增加1的個數(shù)。

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

再說一下查表的原理

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

注意類型轉(zhuǎn)換的時候,先取到n的地址,然后轉(zhuǎn)換為unsigned char*,這樣一個unsigned int(4 bytes)對應(yīng)四個unsigned char(1 bytes),分別取出來計算即可。舉個例子吧,以87654321(十六進制)為例,先寫成二進制形式-8bit一組,共四組,以不同顏色區(qū)分,這四組中1的個數(shù)分別為4,4,3,2,所以一共是13個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] = 
    {
        0112
        1223
        1223
        2334
    } ;

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

靜態(tài)表-8bit

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

第一次(n & 0xff)          10101011110011011110111100010010

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

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

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

int BitCount7(unsigned int n)

    unsigned int table[256] = 
    { 
        0112122312232334
        1223233423343445
        1223233423343445
        2334344534454556
        1223233423343445
        2334344534454556
        2334344534454556
        3445455645565667
        1223233423343445
        2334344534454556
        2334344534454556
        3445455645565667
        2334344534454556
        3445455645565667
        3445455645565667
        4556566756676778
    }; 

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

當(dāng)然也可以搞一個16bit的表,或者更極端一點32bit的表,速度將會更快。

平行算法

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

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 ; 
}

速度不一定最快,但是想法絕對巧妙。說一下其中奧妙,其實很簡單,先將n寫成二進制形式,然后相鄰位相加,重復(fù)這個過程,直到只剩下一位。

以217(11011001)為例,有圖有真相,下面的圖足以說明一切了。217的二進制表示中有5個1

完美法

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

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

第一行代碼的作用

先說明一點,以0開頭的是8進制數(shù),以0x開頭的是十六進制數(shù),上面代碼中使用了三個8進制數(shù)。

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

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

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

然后做減法

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

第二行代碼的作用

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

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

tmp + (tmp >> 3)-這句就是是相鄰組相加,注意會產(chǎn)生重復(fù)相加的部分,比如tmp = 659 = 001 010 010 011時,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只是個中間變量,這個結(jié)果不代表659這個數(shù)的二進制形式中有8個1。

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

位標志法

感謝網(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_countunsigned 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); 
}



推薦閱讀

【1】I2C和SPI總線,嵌入式工程師愛用哪個?

【2】單片機軟件抗干擾的這幾種辦法,以后不能說不知道了

【3】終于整理齊了,電子工程師“設(shè)計錦囊”,你值得擁有!

【4】半導(dǎo)體行業(yè)的人都在關(guān)注這幾個公眾號

我驚呆了!這道C編程面試題居然有如此多的解法!

你和大牛工程師之間到底差了啥?
加入技術(shù)交流群,與高手面對面 
添加管理員微信
我驚呆了!這道C編程面試題居然有如此多的解法!
加入“中國電子網(wǎng)微信群”交流

我驚呆了!這道C編程面試題居然有如此多的解法!
具體加群詳情請戳
“中國電子網(wǎng)技術(shù)交流群” 

免責(zé)聲明:本文內(nèi)容由21ic獲得授權(quán)后發(fā)布,版權(quán)歸原作者所有,本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點,不代表本平臺立場,如有問題,請聯(lián)系我們,謝謝!

21ic電子網(wǎng)

掃描二維碼,關(guān)注更多精彩內(nèi)容

本站聲明: 本文章由作者或相關(guān)機構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫毥谦F公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術(shù)解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關(guān)鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險,如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機 衛(wèi)星通信

要點: 有效應(yīng)對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競爭力 堅持高質(zhì)量發(fā)展策略,塑強核心競爭優(yōu)勢...

關(guān)鍵字: 通信 BSP 電信運營商 數(shù)字經(jīng)濟

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術(shù)學(xué)會聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(shù)(集團)股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉