一道簡單的算法題

題目:統(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é)果下翎。神奇~

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)行測試的結(jié)果宝当。


參考資料:

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市庆揩,隨后出現(xiàn)的幾起案子俐东,更是在濱河造成了極大的恐慌,老刑警劉巖订晌,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件犬性,死亡現(xiàn)場離奇詭異,居然都是意外死亡腾仅,警方通過查閱死者的電腦和手機(jī)乒裆,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來推励,“玉大人鹤耍,你說我怎么就攤上這事肉迫。” “怎么了稿黄?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵喊衫,是天一觀的道長。 經(jīng)常有香客問我杆怕,道長族购,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任陵珍,我火速辦了婚禮寝杖,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘互纯。我一直安慰自己瑟幕,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布留潦。 她就那樣靜靜地躺著只盹,像睡著了一般。 火紅的嫁衣襯著肌膚如雪兔院。 梳的紋絲不亂的頭發(fā)上殖卑,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天,我揣著相機(jī)與錄音坊萝,去河邊找鬼懦鼠。 笑死,一個(gè)胖子當(dāng)著我的面吹牛屹堰,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播街氢,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼扯键,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了珊肃?” 一聲冷哼從身側(cè)響起荣刑,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎伦乔,沒想到半個(gè)月后厉亏,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡烈和,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年爱只,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片招刹。...
    茶點(diǎn)故事閱讀 40,865評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡恬试,死狀恐怖窝趣,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情训柴,我是刑警寧澤哑舒,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站幻馁,受9級(jí)特大地震影響洗鸵,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜仗嗦,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一膘滨、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧儒将,春花似錦吏祸、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至砰逻,卻和暖如春鸣驱,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背蝠咆。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工踊东, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人刚操。 一個(gè)月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓闸翅,卻偏偏與公主長得像,于是被迫代替她去往敵國和親菊霜。 傳聞我的和親對象是個(gè)殘疾皇子坚冀,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容