該代碼如何工作來計算1位的數量？

我發現下面的代碼來計算給定整數的二進制表示中1-bits的數量。任何人都可以解釋它如何工作？而且這些口罩是如何選擇的？謝謝。該代碼如何工作來計算1位的數量？

int count_one(int x) 
{ 
    x = (x & (0x55555555)) + ((x >> 1) & (0x55555555)); 
    x = (x & (0x33333333)) + ((x >> 2) & (0x33333333)); 
    x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f)); 
    x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff)); 
    x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff)); 
    return x; 
}

來源

2014-01-15 herohuyongtao

這是作業嗎？ – Femaref

請參閱http://graphics.stanford.edu/~seander/bithacks.html，搜索「並行計數位設置」。 – paxdiablo

@Femaref不，不是。只是想弄清楚它是如何工作的。 – herohuyongtao

該算法使用x作爲計算的來源和內存。首先，想想位掩碼是什麼：

0x55 = 01010101 
0x33 = 00110011 
0x0f = 00001111 
0xff = 11111111

讓我們有8位例如：A = 01101010

a & 0x55 = 01000000; (a >> 1) & 0x55 = 00010101

如果再加上這兩者結合起來，我們就得到每兩個位的位計數對。該結果最多爲0x10，因爲掩碼只爲每次添加設置一個位。

現在我們使用0x33掩碼，記住每個連續的2位包含第一個操作的結果。用這個掩碼，我們屏蔽掉連續的4位並添加它們。該結果最多爲0x100。這與其他口罩繼續進行，直到我們在x中得到結果。

在紙上試一下，幾步後就會很清楚。

來源

2014-01-15 08:14:20 Femaref

我正在尋找更科學的解決方案。我的意思是，你的回答沒有問題，但我仍然不知道口罩是如何選擇的。 –

掩碼選擇越來越長的連續比特（因爲算法處理32位整數，你需要比我的例子更多的掩碼）。你能告訴我你到底不明白什麼嗎？因爲對我來說，在紙上完成後，這很明顯。 – Femaref

@SilviuBurcea這是面具唯一明顯的選擇，你會怎麼做呢？ – harold

爲了讓這個更容易解釋，讓我假設一個整數是4位長，每一位表示爲1,2,3,4。爲了得到1-bits的數字，您可以先得到1和2的總和以及3和4的總和，然後將這些總和相加。

x & (0x5)將消除1和3，以及x & (0xa)將消除2和4 x & (0x5) + (x & (0xa) >> 1)將使用1個2位來存儲的1之和2，並使用3個4位來存儲的3之和4 x & (0x5) + (x & (0xa) >> 1)是相同作爲x & (0x5) + (x >> 1) & (0x5)。

現在我們有了所有存儲在x中的1 2和3 4的和，我們可以在添加它們之後得到結果。同上，x & (0x3)將得到3 4的總和，並且x & (0x12)將得到1的總和。x & (0x3) + (x & (0x12)) >> 2將得到最終結果。 x & (0x3) + (x & (0x12)) >> 2與x & (0x3) + (x >> 2) & (0x3)相同。

所以你可以看到裏面發生了什麼。就你而言，第一行你可以得到1 2和3 4和5 6的總和，然後繼續。在第二行中，您將得到1 2 3 4和5 6 7 8的總和並繼續。所以通過這樣做5次，你會得到所有32位的數量。

來源

2014-01-15 08:30:31 qqfish

這是一種分而治之的方法。請注意，第一行會給你後續對的和，接下來是後續四倍的和，最後是比特數。

例（16位，所以考慮你的代碼沒有最後一行）

1011001111000110

在拳頭行，我們採取&甚至位和移動一位奇數位。然後我們添加。

對於偶數位：

num: 10 11 00 11 11 00 01 10 
mask: 01 01 01 01 01 01 01 01 
res: 00 01 00 01 01 00 01 00

對於奇數位：

num>>1: 01 01 10 01 11 10 00 11 
mask: 01 01 01 01 01 01 01 01 
res: 01 01 00 01 01 00 00 01

我們添加這些結果，並得到資金在隨後對

01 10 00 10 10 00 01 01

我們重複同樣具有以下口罩和相應的班次

2nd: 0011 0011 0011 0011 
3rd: 0000 1111 0000 1111 
4th: 0000 0000 1111 1111

而我們得到：

2nd: 0011 0010 0010 0010 // 3 set in the first four, 2 in other quadrupels 
3rd: 0000 0101 0000 0100 // 5 bits set in the first eight, 4 in the rest 
4th: 0000 0000 0000 1001 // 9 bits in total

來源

2014-01-15 08:38:18

第一行對待整數爲16 2位整數的數組，該表達式的結果是0，如果在2位對0位被設定如果2位對中的1位被設置（01 bin或10 bin），則爲1，如果2位對中的兩個位均被置位，則爲2。這是因爲我們考慮了x的每兩位的較低位，並且x的每兩位的較低位向右移一位;將它們加在一起。我們知道在2位對之外不會出現進位，因爲我們的加數限制爲0或1.然後將結果存回x。

x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));

下一行做同樣的事情，這一次處理，每2位作爲一個單獨的整數，存儲每4位用於佔據兩個被加數它們的總和。在這個操作之後，整數本質上變成了一個8位4位整數的數組。在操作之前，每個加法器都是0,1或2（十進制），因爲它對應於最後一行的計數。正因爲如此，我們知道每個和不會大於4.由於每個4位int具有最大值15（十進制），所以我們知道這也不會溢出。如上所述，結果存儲回x。

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

我們做與上述相同，此時suming每對4位到每一個組8位組成。

x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));

我們再總結以往對8位到每對16位（的x上部和下部的一半）。

x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));

我們現在總結的x的上半部和下半部，而我們只剩下一個32位的值等於在x值設置的位的數目。

x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));

的這裏關鍵是，每一步確實比特就地成對計數，直到我們留下了在32位整數它自的總比特數。

來源

2014-01-16 16:37:57 Apriori

該代碼如何工作來計算1位的數量？

回答

相關問題