C代码计算未签名char中“ 1”位的数量

StackOverflow https://stackoverflow.com/questions/697978

  •  22-08-2019
  •  | 
  •  

题

我需要C代码才能在C中的未签名字符中返回1的数量。我需要一个解释，即如果它不明显，为什么它有效。我找到了很多32位编号的代码，但对于未签名的字符来说，代码不多。

有帮助吗？

解决方案

相同的代码将适用于未签名的字符。循环在所有测试它们的位上。看 这个.

其他提示

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

请参阅位Twiddling Hacks页面： http://graphics.stanford.edu/~seander/bithacks.html#countbitssetsetkernighan

有许多好的解决方案。

同样，在其最简单的实现中，此功能相当微不足道。您应该花时间学习如何做到这一点。

对于像未签名的炭一样小的整数，您可以使用小型查找桌获得最佳性能。

我知道您要提到哪些人口计数算法。他们通过做算术的算术比存储在寄存器中的整数小的算术来工作。

该技术称为swar（http://en.wikipedia.org/wiki/swar).

有关更多信息，我建议您访问hackers Delight网站：www.hackersdelight.org。他有示例代码，并写了一本书，详细解释了这些技巧。

正如已经回答的那样，计数位的标准方法也适用于未签名的字符。

例子：

    unsigned char value = 91;
int bitCount = 0;
while(value > 0)
{
    if ( value & 1 == 1 ) 
        bitCount++;
    value >>= 1;
}

未签名的char是一个“数字”，就像32位浮点或整数是“数字”一样，编译器认为它们代表的是什么。

如果您将字符描绘成它的位：

01010011（8位）;

您可以通过执行以下操作来计算设定位：

以值为x的值，然后取x％2，其余的将是1或0。也就是说，取决于char的endianness，左或右最多。将其余部分累积在一个单独的变量中（这将是所得的设定位数）。

然后>>（右移）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的帖子，我们有没有分支的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 bits版本，需要9个操作。

int hammingWeight16( const UINT16& c)
{
    return ((c & 0xFF)* 0x8040201ULL & 0x11111111)%0xF + 
             ((c >> 8)* 0x8040201ULL & 0x11111111)%0xF;
}

在这里，我编写了一个需要64位寄存器和11个操作的变体版本。它似乎并不比上一个更好，但它仅使用1个Modulo操作。

int hammingWeight16( const UINT16& c)
{
    UINT64  w;
    w= (((( c* 0x8000400020001ULL)>> 3) & 0x1111111111111111)+14)%0xF;
    return (c!=0)*(w+1+(c==0xFFFF)*15);
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top