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

I need C code to return the number of 1's in an unsigned char in C. I need an explanation as to why it works if it's not obvious. I've found a lot of code for a 32-bit number but not much for an unsigned char.

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

8 个解决方案

#1

The same code will work for an unsigned char. Loop over all bits testing them. See this.

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

#2

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

#3

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

HACKMEM在3个操作中有这个算法(大致翻译为C):

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

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

(ULL是强制64位算术。它是必需的,只是......这个计算需要33位整数。)

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

实际上,您可以用042104210021ULL替换第二个常量,因为您只计算8位,但它看起来不那么对称。

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,请记住(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

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.

如果您没有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

For example, if c == 105 == 0b11001001,

例如,如果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

#4

See the bit twiddling hacks page: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

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

there are many good solutions for this.

有很多很好的解决方案。

Also, this function in its simplest implementation is fairly trivial. You should take the time to learn how to do this.

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

#5

For a integer as small as an unsigned char you get best performance using a small lookup-table.

对于与unsigned char一样小的整数,使用小型查找表可以获得最佳性能。

I know what population-count algorithms you're mentioning. They work by doing arithmetic of multiple words smaller than an integer stored in a register.

我知道你提到的人口数算法。它们通过对比寄存器中存储的整数小的多个单词进行算术运算。

This technique is called SWAR (http://en.wikipedia.org/wiki/SWAR).

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

For more information I suggest you check out the hackers delight website: www.hackersdelight.org. He has example code and written a book that explains these tricks in detail.

有关更多信息,我建议您查看黑客喜悦网站:www.hackersdelight.org。他有示例代码并编写了一本书,详细解释了这些技巧。

#6

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

#7

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.

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

if you picture a char as its bits:

如果你把char描绘成它的位:

01010011 (8 bits);

01010011(8位);

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).

取值,比如x,取x%2,余数为1或0.也就是说,取决于字符的字节顺序,左边或最右边的位。将余数累加在一个单独的变量中(这将是结果的设置位数)。

then >> (right shift) 1 bit.

然后>>(右移)1位。

repeat until 8 bits have been shifted.

重复直到8位被移位。

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

从我的伪代码实现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;
    }
}

#8

-1

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

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

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

应用两次,我们有一个16位版本,需要9次操作。

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.

在这里,我编写了一个16bits版本,需要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);
}

#1