用于计算unsigned char中“1”位数的C代码
我需要C代码在C中的unsigned char中返回1的数量。如果不明显，我需要解释它为什么有效。 我找到了很多32位数的代码，但对于unsigned char却没有多少代码。
相同的代码适用于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的位数。为每个半字节添加结果。
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
有很多很好的解决方案。
此外，这个函数最简单的实现是相当简单的。 你应该花时间学习如何做到这一点。
对于与unsigned char一样小的整数，使用小型查找表可以获得最佳性能。
我知道你提到的人口数算法。 它们通过对比寄存器中存储的整数小的多个单词进行算术运算。
这种技术称为SWAR（ http://en.wikipedia.org/wiki/SWAR ）。
有关更多信息，我建议您查看黑客喜悦网站：www.hackersdelight.org。 他有示例代码并编写了一本书，详细解释了这些技巧。
正如已经回答的那样，计数位的标准方法也适用于无符号字符。
例：
unsigned char value = 91; int bitCount = 0; while(value > 0) { if ( value & 1 == 1 ) bitCount++; value >>= 1; }
unsigned char是一个“数字”，就像32位浮点数或整数是“数字”一样，编译器认为它们代表的是什么变化。
如果你把char描绘成它的位：
01010011（8位）;
您可以通过执行以下操作来计算设置位：
取值，比如x，取x％2，余数为1或0.也就是说，取决于字符的字节顺序，左边或最右边的位。 将余数累加在一个单独的变量中（这将是结果的设置位数）。
然后>>（右移）1位。
重复直到8位被移位。
从我的伪代码实现c代码应该非常简单，但基本上
public static int CountSetBits(char c) { int x = 0; int setBits = 0; while (x < 7) { setBits = setBits + c % 2; c = c >> 1; x = x + 1; } }
基于Ephemient的post，我们有无分支的8位版本。 它是hex表达式。
typedef unsigned char UINT8; typedef unsigned short UINT16; typedef unsigned long long UINT64; int hammingWeight8( const UINT8& c) { return ( c* 0x8040201ULL & 0x11111111)%0xF; }
应用两次，我们有一个16位版本，需要9次操作。
int hammingWeight16( const UINT16& c) { return ((c & 0xFF)* 0x8040201ULL & 0x11111111)%0xF + ((c >> 8)* 0x8040201ULL & 0x11111111)%0xF; }
在这里，我编写了一个16bits版本，需要64位寄存器和11个操作。 它似乎并不比前一个好，但它只使用1个模运算。
int hammingWeight16( const UINT16& c) { UINT64 w; w= (((( c* 0x8000400020001ULL)>> 3) & 0x1111111111111111)+14)%0xF; return (c!=0)*(w+1+(c==0xFFFF)*15); }