我需要C代码在C中的unsigned char中返回1的数量.如果不明显,我需要解释它为什么有效.我找到了很多32位数的代码,但对于unsigned char却没有多少代码.
const unsigned char oneBits[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4}; unsigned char CountOnes(unsigned char x) { unsigned char results; results = oneBits[x&0x0f]; results += oneBits[x>>4]; return results }
有一个知道0到15位数的数组.为每个半字节添加结果.
相同的代码适用于unsigned char.循环遍历测试它们的所有位.看到这个.
HACKMEM在3个操作中有这个算法(大致翻译成C):
bits = (c * 01001001001ULL & 042104210421ULL) % 017;
(ULL
是强制64位算术.这是必需的,只是勉强...这个计算需要33位整数.)
实际上,您可以用第二个常量替换042104210021ULL
,因为您只计算8位,但它看起来不那么对称.
这是如何运作的?想一想c
,并记住(a + b) % c = (a % c + b % c) % c
,和(a | b) == a + b
iff (a & b) == 0
.
(c * 01001001001ULL & 042104210421ULL) % 017 01 01001001001 01 1 02 02002002002 02000000000 1 04 04004004004 04000000 1 010 010010010010 010000 1 020 020020020020 020 1 040 040040040040 040000000000 1 # 040000000000 == 2 ** 32 0100 0100100100100 0100000000 1 0200 0200200200200 0200000 1
如果您没有64位算术可用,您可以分成c
半字节并执行每一半,执行9次操作.这只需要13位,因此使用16位或32位算法将起作用.
bits = ((c & 017) * 0421 & 0111) % 7 + ((c >> 4) * 0421 & 0111) % 7; (c * 0421 & 01111) % 7 1 0421 01 1 2 01042 01000 1 4 02104 0100 1 8 04210 010 1
例如,如果c == 105 == 0b11001001
,
c == 0100 | 040 | 010 | 01 == 0151 * 01001001001001ULL == 0100100100100 | 040040040040 | 010010010010 | 01001001001 == 0151151151151 & 0421042104210421ULL == 0100000000 | 04000000000 | 010000 | 01 == 04100010001 % 017 == 4 c & 017 == 8 | 1 == 011 011 * 0421 == 8 * 0421 | 1 * 0421 == 04210 | 0421 == 04631 04631 & 0111 == 04210 & 0111 | 0421 & 0111 == 010 | 01 == 011 011 % 7 == 2 c >> 4 == 4 | 2 == 06 06 * 0421 == 4 * 0421 | 2 * 0421 == 02104 | 01042 == 03146 03146 & 0111 == 02104 & 0111 | 01042 & 0111 == 0100 | 01000 == 01100 01100 % 7 == 2 2 + 2 == 4
请参阅bit twiddling hacks页面:http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
有很多很好的解决方案.
此外,这个函数在其最简单的实现中是相当简单的.你应该花时间学习如何做到这一点.