如何仅使用按位运算符实现Bitcount?
任务是仅使用按位运算符实现位计数逻辑。 我的工作正常,但我想知道是否有人可以提出更优雅的方法。
只允许使用Bitwise操作。 没有“如果”,“为”等
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);
谢谢。
来自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);
这五个中的每一步,将相邻的位组合在一起,然后是2,然后是4等。该方法基于分而治之。
在第一步中,我们将位0和1加在一起,并将结果放在两位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,这是正确的结果
我会使用预先计算的数组
uint8_t set_bits_in_byte_table[ 256 ];
该表中的第i
个条目存储字节i
的设置位数,例如set_bits_in_byte_table[ 100 ] = 3
因为十进制100的二进制表示中有3个1
位(= 0x64 = 0110-0100)。
然后我会试试
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; }
这是答案的简单说明:
abcd 0 abc 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位来存储+ b和2位来存储c + d。 a = 0,1等,所以2位是我们需要存储它们的总和。 在下一步,我们将有4位来存储2位值的总和等。
几个有趣的解决方案。
如果上面的解决方案太无聊,这里是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));