用于计算unsigned char中"1"位数的C代码

Question

我需要C代码在C中的unsigned char中返回1的数量.如果不明显,我需要解释它为什么有效.我找到了很多32位数的代码,但对于unsigned char却没有多少代码.

Answer 1

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位数的数组.为每个半字节添加结果.

Answer 2

相同的代码适用于unsigned char.循环遍历测试它们的所有位.看到这个.

Answer 3

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 + biff (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

Answer 4

请参阅bit twiddling hacks页面:http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

有很多很好的解决方案.

此外,这个函数在其最简单的实现中是相当简单的.你应该花时间学习如何做到这一点.