我需要一段 C 代码来返回一个无符号字符中1的数量。如果不明显，我需要解释为什么它起作用。我已经找到了很多32位数字的代码，但是对于无符号字符的代码并不多。
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位的比特数。将每个半字节的结果相加。
- Robert
1
不错。我也是这样做的，但是省去了除法和取模运算。 - Chris Doggett
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)==0时，(a|b)==a+b。 (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
- ephemient
2
1当你在0x77上运行你的算法时，会得到什么结果？ - Andre Artus
@AndreArtus 你得到了6。 - splch
5
请参见位操作技巧页面：http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan。
有许多好的解决方案可供选择。
此外，这个函数的简单实现相当简单。您应该花时间学习如何做到这一点。
有许多好的解决方案可供选择。
此外，这个函数的简单实现相当简单。您应该花时间学习如何做到这一点。
- Evan Teran
3
对于像无符号字符这样小的整数，使用一个小的查找表可以获得最佳性能。
我知道你提到的人口数量算法。它们通过在寄存器中存储的整数多个小于一个整数的字进行算术运算来工作。
这种技术称为SWAR（http://en.wikipedia.org/wiki/SWAR）。
要了解更多信息，建议您访问hackers delight网站：www.hackersdelight.org。他有示例代码，并撰写了一本详细解释这些技巧的书。
- Nils Pipenbrinck
0
如已经回答的那样，计算比特位的标准方法也适用于无符号字符。
例如：
unsigned char value = 91;
int bitCount = 0;
while(value > 0)
{
if ( value & 1 == 1 )
bitCount++;
value >>= 1;
}
- driis
1
这相当糟糕。
1）不必要的检查（value> 0）。使用while（value）通常会更好。在x86上从性能角度来看，这并不重要，但在其他架构上可能会有所影响。
2）内部循环中的分支是不必要且相当糟糕的，bitCount + = value＆1更好。
3）迭代所有8位而不是直到结果为0可能会展开循环，并在大多数常见架构上编译成8对shr，adc。当然，只使用LUT会更好。 - 3yE
-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;
}
应用它两次，我们就有了一个16位版本，需要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);
}
- jemin
-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;
}
}
- Bigdubs
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接