4

Possible Duplicate:
Best algorithm to count the number of set bits in a 32-bit integer?

Hello,

Is there a more compact way of counting the number of ones in a byte without using a loop? I don't want to do the following if I don't have to. Thanks.

char myValue = 0x0F;

int counter = 0;

while (myValue > 0)
{
 if (myValue & 0x01)
 {
  counter ++;
 }

 myValue = myValue >> 1;
}
Community
  • 1
  • 1
David
  • 14,205
  • 20
  • 97
  • 144
  • 5
    Possible duplicate of http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer – vitaut Jan 26 '11 at 15:29
  • Are you asking for a solution in C? C++? objective-c? These are all very different languages. The solution is going to be slightly different for each one. – wheaties Jan 26 '11 at 15:31
  • @wheaties: I'm pretty sure C and C++ don't differ here. – Paul Nathan Jan 26 '11 at 15:33
  • @vitaut: not a duplicate question, but there's definitely a duplicate answer. – Paul Nathan Jan 26 '11 at 15:35
  • 2
    @Paul Nathan in C++ I'd just put it into a `std::bitset` and then call the `bitset::count` function. In C, that doesn't exist. – wheaties Jan 26 '11 at 15:36
  • C, C++, objective-c at this level are approximatively equivalent. Only a few general purpose processor provide bitcount instruction. This instruction has been introduced on x86 when the MMX instruction set has been added. – VGE Jan 26 '11 at 15:38

2 Answers2

8
 ((i>>3)&1)+((i>>2)&1)+((i>>1)&1)+(i&1)

Or use assembly (SSE/MMX). http://gurmeet.net/puzzles/fast-bit-counting-routines/

VGE
  • 4,171
  • 18
  • 17
  • Your code is a sum of four brackets, each bracket can be either 0 or 1. So the result can be at most four, but there can be 8 ones in a Byte. – Ivan Kuckir Apr 07 '20 at 21:48
0

This works if you initialize the table correctly.

static const unsigned char one_bits_in_byte[] = { 0, 1, 1, 2, 1, ... };

int counter = one_bits_in_byte[myValue & 0xFF];

Of course, you'd write a program with a loop in it to generate the table so that your final program doesn't have a loop in it. If you are feeling cost conscious, you can encode just the data for 0..15 and process the two halves (nybbles) of the value with shifts. But with 24 GB of physical memory, this is unlikely to be a major problem. And you could also simply compute the value on demand with masking operations, etc (like VGE suggests, but extended to a whole byte).

Community
  • 1
  • 1
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278