如何不用循環(huán)與任何控制語句得到一個(gè)二進(jìn)制數(shù)中１的個(gè)數(shù)
在做CSAPP的Datalab的過程中筛峭，有一道題目讓你在不用循環(huán)與任何控制語句的情況下得到一個(gè)二進(jìn)制數(shù)中１的個(gè)數(shù)。乍一看這好像是不可能完成的，但是又聯(lián)想到了int類型的大小是有限的领斥，于是可以用如下的方法來解決嫉拐。
int bitcount(int x){
int mask = 0x01;
int sum = 0;
sum = sum + (x & mask);
sum = sum + (x >> 1 & mask);
sum = sum + (x >> 2 & mask);
sum = sum + (x >> 3 & mask);
sum = sum + (x >> 4 & mask);
sum = sum + (x >> 5 & mask);
sum = sum + (x >> 6 & mask);
sum = sum + (x >> 7 & mask);
sum = sum + (x >> 8 & mask);
sum = sum + (x >> 9 & mask);
sum = sum + (x >> 10 & mask);
sum = sum + (x >> 11 & mask);
sum = sum + (x >> 12 & mask);
sum = sum + (x >> 13 & mask);
sum = sum + (x >> 14 & mask);
sum = sum + (x >> 15 & mask);
sum = sum + (x >> 16 & mask);
sum = sum + (x >> 17 & mask);
sum = sum + (x >> 18 & mask);
sum = sum + (x >> 19 & mask);
sum = sum + (x >> 20 & mask);
sum = sum + (x >> 21 & mask);
sum = sum + (x >> 22 & mask);
sum = sum + (x >> 23 & mask);
sum = sum + (x >> 24 & mask);
sum = sum + (x >> 25 & mask);
sum = sum + (x >> 26 & mask);
sum = sum + (x >> 27 & mask);
sum = sum + (x >> 28 & mask);
sum = sum + (x >> 29 & mask);
sum = sum + (x >> 30 & mask);
sum = sum + (x >> 31 & mask);
return(sum);
}
注:此示例為３２位，６４位方法完全相同.(使用循環(huán)的克尼漢算法與此原理完全相同)
但這樣的樸素方法有點(diǎn)太愚笨了税娜，而且也不符合題目給出的操作符數(shù)量限制坐搔。經(jīng)過查閱資料，我發(fā)現(xiàn)了如下的一種算法
int swar(uint32_t i) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
| i | j | i-j |
|---|---|---|
| 00 | 00 | 00 |
| 01 | 00 | 01 |
| 10 | 01 | 01 |
| 11 | 01 | 10 |
emmmmm這是什么鬼???=.=
接下來我就找到了一篇講解此算法的文章
magic
經(jīng)過一番研究敬矩，算是弄明白了這個(gè)奇妙的算法概行。
我們接下來一行一行地看這個(gè)算法。
首先弧岳，第一行凳忙，我們令j = (i >> 1) & 0x55555555.接下來，我們看一下為什么要設(shè)這個(gè)0x55555555. 0x55555555寫成二進(jìn)制為0b01010101010101010101010101010101,接下來我們我們記i的前幾位為$ i_1i_2i_3i_4i_5i_6i_7i_8 $, 那么ｊ的結(jié)果為$0i_10i_30i_50i_7$.這個(gè)算法的巧妙之處便在于此中非常重要的一點(diǎn)禽炬。我們兩位兩位地去看i-j這個(gè)數(shù)消略，可能有以下幾種情況
| i | j | i-j |
|---|---|---|
| 00 | 00 | 00 |
| 01 | 00 | 01 |
| 10 | 01 | 01 |
| 11 | 01 | 10 |
也就是說，i-j的結(jié)果的值就是i中１的數(shù)量.于是瞎抛，我們把整個(gè)int分成數(shù)個(gè)2bit的塊艺演，在每個(gè)塊內(nèi)我們已經(jīng)完成了此問題，接下來就是要把整個(gè)結(jié)果聚合起來.
第二行與第三行的前半部分完成的就是這個(gè)工作。i = (i & 0x33333333) + ((i >> 2) & 0x33333333);(i + (i >> 4)) & 0x0F0F0F0F)這兩部分代碼分別把兩位的結(jié)果聚合到了四位與八位胎撤。再接下來我們?nèi)コ说倪@個(gè)數(shù)0x01010101,相當(dāng)于做了這樣一件事:$k * 0x01010101 = (k << 24) + (k << 16) + (k << 8) + k$這樣一來最高位的字節(jié)就是結(jié)果了晓殊，我們只需把它移動(dòng)到最低位就得到了答案。
