当前位置：文江博客话题详情

C 代码计算“1”的数量无符号字符中的位

发布于 2024-07-16 06:24:27 字数 92 浏览 9 评论 0原文

我需要 C 代码来返回 C 中无符号字符中 1 的数量。如果不明显，我需要解释为什么它可以工作。我找到了很多 32 位数字的代码，但没有找到太多用于无符号字符的代码。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

别靠近我心 2024-07-23 06:24:27

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 位数的数组。将每个半字节的结果相加。

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
}

Have an array that knows the number of bits for 0 through 15. Add the results for each nibble.

回复收藏 0 原文

夏有森光若流苏 2024-07-23 06:24:27

相同的代码适用于无符号字符。循环测试它们的所有位。请参阅此。

回复收藏 0 原文

轮廓§ 2024-07-23 06:24:27

HACKMEM 在 3 个操作中使用此算法（大致翻译为 C）：（

bits = (c * 01001001001ULL & 042104210421ULL) % 017;

ULL是强制64位算术。这是需要的，只是勉强......这个计算需要33位整数。）

实际上，你可以用042104210021ULL替换第二个常量 code>，因为你只计算 8 位，但它看起来不太对称。

这是如何运作的？按位思考 c，并记住 (a + b) % c = (a % c + b % c) % c 和 (a | b) == a + b 当且仅当(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

HACKMEM has this algorithm in 3 operations (roughly translated to C):

bits = (c * 01001001001ULL & 042104210421ULL) % 017;

(ULL is to force 64-bit arithmetic. It's needed, just barely... this calculation requires 33-bit integers.)

Actually, you can replace the second constant with 042104210021ULL, since you're only counting 8 bits, but it doesn't look as nicely symmetrical.

How does this work? Think of c bit-wise, and remember that (a + b) % c = (a % c + b % c) % c, and (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

If you don't have 64-bit arithmetic available, you can split c up into nibbles and do each half, taking 9 operations. This only requires 13 bits, so using 16- or 32-bit arithmetic will work.

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

For example, if 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

回复收藏 0 原文

冧九 2024-07-23 06:24:27

请参阅位旋转黑客页面：http://graphics.stanford.edu/~seander/ bithacks.html#CountBitsSetKernighan

对于这个问题有很多好的解决方案。

此外，这个函数在其最简单的实现中是相当简单的。您应该花时间学习如何执行此操作。

回复收藏 0 原文

孤星 2024-07-23 06:24:27

对于像无符号字符一样小的整数，您可以使用小型查找表获得最佳性能。

我知道你提到的人口计数算法。它们的工作原理是对小于寄存器中存储的整数的多个字进行算术。

这种技术称为 SWAR (http://en.wikipedia.org/wiki/SWAR) 。

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

回复收藏 0 原文

剪不断理还乱 2024-07-23 06:24:27

正如已经回答的那样，计算位的标准方法也适用于无符号字符。

例子：

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

As already answered, the standard ways of counting bits also work on unsigned chars.

Example:

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

回复收藏 0 原文

夜血缘 2024-07-23 06:24:27

unsigned char 是一个“数字”，就像 32 位浮点数或整数是一个“数字”一样，编译器认为它们代表的就是变化。

如果你把一个字符想象成它的位：

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;
    }
}

an unsigned char is a "number" in just the same way that a 32-bit float or integer is a "number", what the compiler deems them to represent is what changes.

if you picture a char as its bits:

01010011 (8 bits);

you can count the set bits by doing the following:

take the value, lets say x, and take x % 2, the remainder will be either 1 or 0. that is, depending on the endianness of the char, the left or right most bit. accumulate the remainder in a separate variable (this will be the resulting number of set bits).

then >> (right shift) 1 bit.

repeat until 8 bits have been shifted.

the c code should be pretty simple to implement from my pseudocode, but basically

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;
    }
}

回复收藏 0 原文

飘然心甜 2024-07-23 06:24:27

根据 Ehemient 的帖子，我们有无分支的 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);
}

base on Ephemient's post, we have the no branched 8 bits version. It is in hexadecimal expression.

typedef unsigned char       UINT8;
typedef unsigned short      UINT16;
typedef unsigned long long  UINT64;
int hammingWeight8( const UINT8& c)
{
    return ( c* 0x8040201ULL & 0x11111111)%0xF;
}

Apply it twice, we have a 16bits version, which needs 9 operations.

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

Here I write a variant 16bits version which needs 64bits registers and 11 operations. It seems not better than the previous one, but it just uses 1 modulo operation.

int hammingWeight16( const UINT16& c)
{
    UINT64  w;
    w= (((( c* 0x8000400020001ULL)>> 3) & 0x1111111111111111)+14)%0xF;
    return (c!=0)*(w+1+(c==0xFFFF)*15);
}

回复收藏 0 原文

~没有更多了~