views:

2877

answers:

8

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.

+13  A: 

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

dirkgently
+5  A: 

See the bit twiddling hacks page: 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.

Evan Teran
+3  A: 

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

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

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.

Nils Pipenbrinck
A: 

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;
    }
}
Will Charczuk
A: 

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;
}
driis
3yE
A: 

Picking on Bigdubs' and driis' replies, how about using a "for" instead of a "while"?

unsigned char i=(unsigned char)value;
unsigned long bitCount=0;
for(i=91; i>0; value>>=1) if(value & 1 == 1) bitCount++;
jbatista
why do you bother assigning value to i in the first line and why do you have i count (arbitrarily) from 92 to 0? You don't need the i variable at all. Just replace "i>0" with "value != 0" and it'll work fine without this nonsense.
Evan Teran
my guess is he didn't realize the 91 was an arbitrary value in driis's example? Anyway J. Batista, using a while loop is better for code maintenance because you wouldn't need to change loop if you change the size of the value.
Mr. Shiny and New
+11  A: 
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.

Robert
Nice. Same way I do it, but saving a division and modulus.
Chris Doggett
+3  A: 

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
ephemient
What do you get when you run your algorithm on 0x77?
Andre Artus