C语言 如何仅使用按位运算符实现 Bitcount？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3815165/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to implement Bitcount using only Bitwise operators?
提问by James Raitsev
The task is to implement a bit count logic using only bitwise operators. I got it working fine, but am wondering if someone can suggest a more elegant approach.
任务是仅使用按位运算符实现位计数逻辑。我让它工作正常，但我想知道是否有人可以提出更优雅的方法。
Only Bitwise ops are allowed. No "if", "for" etc
只允许按位操作。没有“如果”、“为”等
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);
Thank you.
谢谢你。
回答by iniju
From http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
来自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;
Edit: Admittedly it's a bit optimized which makes it harder to read. It's easier to read as:
编辑：诚然，它有点优化，这使得它更难阅读。更容易阅读为：
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);
Each step of those five, adds neighbouring bits together in groups of 1, then 2, then 4 etc. The method is based in divide and conquer.
这五个步骤中的每一步都将相邻的位以 1、2、4 等为一组相加。该方法基于分而治之。
In the first step we add together bits 0 and 1 and put the result in the two bit segment 0-1, add bits 2 and 3 and put the result in the two-bit segment 2-3 etc...
在第一步中，我们将第 0 位和第 1 位相加并将结果放在两个位段 0-1 中，将第 2 位和第 3 位相加并将结果放在两个位段中 2-3 等...
In the second step we add the two-bits 0-1 and 2-3 together and put the result in four-bit 0-3, add together two-bits 4-5 and 6-7 and put the result in four-bit 4-7 etc...
第二步，我们将两位 0-1 和 2-3 相加并将结果放入四位 0-3，将两位 4-5 和 6-7 相加并将结果放入四位4-7 等...
Example:
例子：
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 )
which is equal to 5, which is the correct result
等于5，这是正确的结果
回答by Arun
I would use a pre-computed array
我会使用预先计算的数组
uint8_t set_bits_in_byte_table[ 256 ];
The i-th entry in this table stores the number of set bits in byte i, e.g. set_bits_in_byte_table[ 100 ] = 3since there are 3 1bits in binary representation of decimal 100 (=0x64 = 0110-0100).
i此表中的第 -th 条目存储字节中设置的位数i，例如，set_bits_in_byte_table[ 100 ] = 3因为1十进制 100 的二进制表示中有 3位（=0x64 = 0110-0100）。
Then I would try
然后我会尝试
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;
}
回答by irudyak
Here's a simple illustration to the 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
So we have exactly 2 bits to store a + b and 2 bits to store c + d. a = 0, 1 etc., so 2 bits is what we need to store their sum. On the next step we'll have 4 bits to store sum of 2-bit values etc.
所以我们正好有 2 位来存储 a + b 和 2 位来存储 c + d。a = 0、1 等，所以我们需要 2 位来存储它们的总和。在下一步中，我们将有 4 位来存储 2 位值的总和等。
回答by e2-e4
Several interesting solutions here.
这里有几个有趣的解决方案。
If the solutions above are too boring, here is a C recursive version exempt of condition test or loop:
如果上面的解决方案太无聊，这里有一个免条件测试或循环的 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));
