在32位整數

尋找在這個link計數位設置的方法計算設定比特的方法的說明，我發現下面的方法在32位整數

作者說：

最好在一個32位的整數v計數位的方法是以下：

v = v - ((v >> 1) & 0x55555555);     // reuse input as temporary 
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);  // temp 
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

最佳位計數方法只需要12個操作，即與查找表方法相同，但避免了內存和潛在的緩存未命中表。它是上面純粹並行的方法和使用乘法的早期方法（在關於對64位指令進行計數的部分中的部分爲）之間的混合，儘管它不使用64位指令。在字節中設置的位的計數在並行中完成，並且通過乘以0x1010101並向右移位24位來計算在字節中設置的位的總和。

任何解釋如何這個方法計數設置位？

來源

2013-04-12 MOHAMED

用手在紙上看看發生了什麼。 –

第一行存儲該對中每對比特的設置比特數。第二個添加兩個相鄰位對的計數並將其存儲在由這兩對組成的半字節中。第三個添加組成一個字節的兩個半字節的計數，然後將所有四個字節的計數相加;與「0x1010101」相乘將每個字節的內容移動到最重要的位置並導致相加。 –

一本名爲「hacker's.delight」的書有更多細節。 – MYMNeo

它的工作，因爲你可以通過劃分成兩半，在兩半計數設置位的數量，然後將其添加了設置位計數的總數。也知道作爲Divide and Conquer範例。讓我們來看看詳細..

v = v - ((v >> 1) & 0x55555555);

位的兩個位的數量可以是0b00，0b01或0b10。讓我們試着來解決這一問題上的2位..

--------------------------------------------- 
| v | (v >> 1) & 0b1010 | v - x | 
--------------------------------------------- 
    0b00   0b00    0b00 
    0b01   0b00    0b01  
    0b10   0b01    0b01 
    0b11   0b01    0b10

這是需要什麼，最後一列顯示的位集合中每兩個位對計數。如果兩位數是>= 2 (0b10)，則and產生0b01，否則產生0b00。

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

該聲明應該易於理解。在第一次操作後，我們每兩位都有設定位數，現在我們每4位總結一次。

v & 0b11001100   //masks out even two bits 
(v >> 2) & 0b11001100 // masks out odd two bits

然後，我們總結了上述結果，使我們能夠在4 bits.The最後一條語句設置位的總數是最棘手的。

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

讓我們進一步分析..

v + (v >> 4)

其類似於第二份聲明，我們是在4組計數設置位來代替。我們知道，由於我們以前的操作，每個半字節都有其中的設定位數。讓我們看一個例子，假設我們有字節0b01000010。這意味着第一個半字節設置爲4位，第二個設置爲2位。現在我們將這些小節加在一起。

0b01000010 + 0b01000000

它爲我們提供了一組位的計數字節，在第一個半字節0b01100010，因此，我們掩蓋了最後四個字節的所有字節的數量（丟棄它們）。

0b01100010 & 0xF0 = 0b01100000

現在每個字節都有設定位數。我們需要將它們加在一起。訣竅是將結果乘以0b10101010，這有一個有趣的屬性。如果我們的號碼有四個字節0，它將產生一個新的號碼，這些字節爲A+B+C+D B+C+D C+D D。一個4字節的數字最多可以設置32位，可以表示爲0b00100000。

我們現在需要的是第一個字節，它具有所有字節中所有設置位的總和，我們通過>> 24得到它。該算法專爲32 bit單詞設計，但可以輕鬆修改爲64 bit單詞。

來源

2013-04-12 10:12:50 vidit

好的回答很好解釋謝謝 – MOHAMED

你應該添加這個答案仍然是開放的問題：http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a -32位整數。它比那裏的大多數答案要好得多。 –

@ BaileyS-我會在那裏添加它。謝謝！ :) – vidit

關於漢明重量的維基百科文章的代碼至少有文件記錄，並且從更一般的概念到超快速12版本的操作都非常全面。

//This uses fewer arithmetic operations than any other known 
//implementation on machines with fast multiplication. 
//It uses 12 arithmetic operations, one of which is a multiply. 
int popcount_3(uint64 x) { 
    x -= (x >> 1) & m1;    //put count of each 2 bits into those 2 bits 
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;  //put count of each 8 bits into those 8 bits 
    return (x * h01)>>56; //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}

http://en.wikipedia.org/wiki/Hamming_weight

來源

2013-04-12 09:16:20

回答

相關問題