我需要 C 代码来返回 C 中 unsigned char 中 1 的数量。如果不明显，我需要解释为什么它可以工作。我发现了很多 32 位数字的代码，但对于 unsigned char 却没有多少。
rlbond
问问题
29303 次
8 回答
20
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 的位数。将每个半字节的结果相加。
于 2009-03-30T17:07:42.437 回答
15
相同的代码适用于无符号字符。循环测试它们的所有位。看到这个。
于 2009-03-30T16:42:35.070 回答
7
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
于 2009-03-30T17:28:05.103 回答
5
请参阅 bit twiddling hacks 页面： http: //graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
有很多很好的解决方案。
此外，这个函数在其最简单的实现中是相当微不足道的。你应该花时间学习如何做到这一点。
于 2009-03-30T16:42:35.837 回答
3
对于像 unsigned char 这样小的整数，您可以使用小型查找表获得最佳性能。
我知道你提到的人口计数算法。它们通过对小于寄存器中存储的整数的多个字进行算术运算来工作。
这种技术称为 SWAR ( http://en.wikipedia.org/wiki/SWAR )。
有关更多信息，我建议您查看骇客喜悦网站：www.hackersdelight.org。他有示例代码并写了一本书详细解释了这些技巧。
于 2009-03-30T16:43:19.967 回答
0
正如已经回答的那样，计数位的标准方法也适用于无符号字符。
例子：
unsigned char value = 91;
int bitCount = 0;
while(value > 0)
{
if ( value & 1 == 1 )
bitCount++;
value >>= 1;
}
于 2009-03-30T16:50:53.977 回答
-1
unsigned char 是一个“数字”，就像 32 位浮点数或整数是一个“数字”一样，编译器认为它们代表的是什么变化。
如果你把一个 char 想象成它的位：
01010011（8位）；
您可以通过执行以下操作来计算设置位：
取值，假设 x，取 x % 2，余数将为 1 或 0。也就是说，取决于 char 的字节序，最左边或最右边。将余数累积在一个单独的变量中（这将是设置位的结果数量）。
然后 >>（右移）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;
}
}
于 2009-03-30T16:43:56.143 回答
-1
根据 Ephemient 的帖子，我们有没有分支的 8 位版本。它是十六进制表达式。
typedef unsigned char UINT8;
typedef unsigned short UINT16;
typedef unsigned long long UINT64;
int hammingWeight8( const UINT8& c)
{
return ( c* 0x8040201ULL & 0x11111111)%0xF;
}
应用两次，我们有一个 16bits 的版本，需要 9 次操作。
int hammingWeight16( const UINT16& c)
{
return ((c & 0xFF)* 0x8040201ULL & 0x11111111)%0xF +
((c >> 8)* 0x8040201ULL & 0x11111111)%0xF;
}
在这里，我编写了一个 16 位版本的变体，它需要 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);
}
于 2016-03-15T19:29:15.510 回答