如何僅使用按位運算符來實現Bitcount？

任務是僅使用按位運算符來實現位計數邏輯。我知道它工作正常，但我想知道是否有人可以建議一個更優雅的方法。如何僅使用按位運算符來實現Bitcount？

只有按位老年退休金計劃是允許的。沒有「if」，「for」等

int x = 4; 

printf("%d\n", x & 0x1); 
printf("%d\n", (x >> 1) & 0x1); 
printf("%d\n", (x >> 2) & 0x1); 
printf("%d\n", (x >> 3) & 0x1);

謝謝。

來源

2010-09-28 JAM

從http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

unsigned int v; // count bits set in this (32-bit value) 
unsigned int c; // store the total here 

c = v - ((v >> 1) & 0x55555555); 
c = ((c >> 2) & 0x33333333) + (c & 0x33333333); 
c = ((c >> 4) + c) & 0x0F0F0F0F; 
c = ((c >> 8) + c) & 0x00FF00FF; 
c = ((c >> 16) + c) & 0x0000FFFF;

編輯：不可否認這是優化了一下這使得它難以閱讀。它更容易爲已讀：

c = (v & 0x55555555) + ((v >> 1) & 0x55555555); 
c = (c & 0x33333333) + ((c >> 2) & 0x33333333); 
c = (c & 0x0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F); 
c = (c & 0x00FF00FF) + ((c >> 8) & 0x00FF00FF); 
c = (c & 0x0000FFFF) + ((c >> 16)& 0x0000FFFF);

這五個的每一個步驟中，以1組，然後2將相鄰比特一起，然後4等該方法是基於在分而治之。

在第一步驟中，我們加在一起的位0和1，並把其結果在2位比特段0-1，添加位2和3，並把結果在這兩個位段2-3等...

在第二步驟中，我們將兩個比特0-1和2-3在一起並把結果在四比特0-3，添加在一起的兩個比特4-5和6-7，並把結果在四比特4-7等...

實施例：

So if I have number 395 in binary 0000000110001011 (0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1) 
After the first step I have:  0000000101000110 (0+0 0+0 0+0 0+1 1+0 0+0 1+0 1+1) = 00 00 00 01 01 00 01 10 
In the second step I have:  0000000100010011 (00+00 00+01 01+00 01+10) = 0000 0001 0001 0011 
In the fourth step I have:  0000000100000100 ( 0000+0001  0001+0011 ) = 00000001 00000100 
In the last step I have:   0000000000000101 (  00000001+00000100  )

等於5，其是正確的結果

來源

2010-09-28 17:06:48 iniju

謝謝你的總和。我很抱歉，我不完全明白爲什麼這會起作用。你能解釋一下嗎 – JAM 2010-09-28 17:11:14

我增加了一個解釋，花了一段時間，因爲我不得不弄清楚發生了什麼。 +1你的問題迫使我明白了：P – iniju 2010-09-28 17:53:07

也看到這個答案，它通過這個功能一步一步走：http://stackoverflow.com/a/15979139/31818 – seh 2013-10-02 00:29:30

一些有趣的解決方案here。

如果上述的解決方案過於無聊，這裏是一個C遞歸版本豁免條件試驗或循環的：

int z(unsigned n, int count); 
    int f(unsigned n, int count); 

    int (*pf[2])(unsigned n, int count) = { z,f }; 

    int f(unsigned n, int count) 
    { 
    return (*pf[n > 0])(n >> 1, count+(n & 1)); 
    } 

    int z(unsigned n, int count) 
    { 
    return count; 
    } 

    ... 
    printf("%d\n", f(my_number, 0));

來源

2010-09-28 17:12:36

我會用一個預先計算的陣列

uint8_t set_bits_in_byte_table[ 256 ];

的i - th表中的條目存儲了字節i中的設置位數，例如set_bits_in_byte_table[ 100 ] = 3，因爲在小數點100（= 0x64 = 0110-0100）的二進制表示中有3個1位。

然後我會嘗試

size_t count_set_bits(uint32_t x) { 
    size_t count = 0; 
    uint8_t * byte_ptr = (uint8_t *) &x; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    return count; 
}

來源

2010-09-28 19:27:38 Arun

這裏有一個簡單的例子給answer：

a b c d  0 a b c  0 b 0 d  
&    &    + 
0 1 0 1  0 1 0 1  0 a 0 c 
-------  -------  ------- 
0 b 0 d  0 a 0 c  a+b c+d

所以我們恰好有2位來存儲A + B和2位器C + d。 a = 0,1等等，所以2位是我們需要存儲它們的總和。在接下來的步驟中，我們將有4位來存儲2位值等

來源

2016-08-25 16:24:46 irudyak

如何僅使用按位運算符來實現Bitcount？

回答

相關問題