設置位計數的數量的整數

可能重複：
Best algorithm to count the number of set bits in a 32-bit integer?設置位計數的數量的整數

嗨，

我在接受採訪時碰到這個問題就來了。我想以優化的方式找到給定數字中的設置位數。

實施例：

如果給定的數目爲7，則輸出應該是3（因爲7個二進制爲111，我們有三個1S）

如果給定的8號然後輸出應該是1（由於二進制8是1000我們有一個1s）

我們需要找到一個優化的方式。有什麼建議麼？

來源

2011-03-18 Mojoy

嘗試使用POPCNT指令。 – mvds 2011-03-18 21:22:03

看看[BitTickedling Hacks]（http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive）中的「Counting Bits Set」 – Ani 2011-03-18 21:22:19

你的問題不清楚。什麼是「位數字段」？個人1位的數量？或從第一個1位到最後一個位的寬度？你提供的例子選擇不好。他們不明確。例如，10位的「位數字」是什麼，二進制中的「1010」是什麼？是2還是3？ – AnT 2011-03-18 21:41:15

概念這個作品：

int numones(int input) { 
    int num = 0; 
    do { 
     num += input % 2; 
     input = input/2; 
    } while (input > 0); 
    return num; 
}

更優化的方式（從上面提意見link）：

unsigned int v; // count the number of bits set in v 
unsigned int c; // c accumulates the total bits set in v 
for (c = 0; v; c++) 
{ 
    v &= v - 1; // clear the least significant bit set 
}

來源

2011-03-18 21:23:32

如果使用GCC，使用內置函數int __builtin_popcount (unsigned int x)。在某些機器上，這會減少到單個指令。

來源

2011-03-18 21:54:26

，但__builtin_popcount（unsigned int x）不會在單個指令中執行此操作。它隱含地執行前面描述的方法。 – 2011-05-03 15:28:23

@gunner有時候它是一個函數，但有時如果芯片有一條popcount指令，它有一個指令代替它，至少根據我讀過的知識。 – 2011-05-03 17:02:54

沃倫有關於計數位的全部內容，包括一個關於Conting 1位的內容。

這個問題可以用分而治之的方式來解決，也就是求和32位，求和2 16位數等等。這意味着我們只需將兩個n位字段中的數字一起添加到一個2n字段中。

Example: 
10110010 
01|10|00|01 
0011|0001 
00000100

該代碼，這看起來是這樣的：

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

我們使用（（x >> 1）& 0x55555555），而不是（X & 0xAAAAAAAA）>> 1僅僅是因爲我們希望避免在寄存器中生成兩個大的常量。如果你看看它，你可以看到最後一個也是無用的，其他的也可以省略，如果不存在這個總和將繼續存在的危險。因此，如果我們簡化代碼，我們結束了這一點：

int pop(unsigned x) { 
    x = x - ((x >> 1) & 0x55555555); 
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333); 
    x = (x + (x >> 4)) & 0x0f0f0f0f; 
    x = x + (x >> 8); 
    x = x + (x >> 16); 
    return x & 0x0000003f; 
}

這會是21級的指令，分公司免費常規RISC機器上。根據平均設置多少位，它可能比kerrigan循環更快或更慢 - 儘管也可能取決於所使用的CPU。

來源

2011-03-19 11:22:29 Voo

設置位計數的數量的整數

回答

相關問題