number of 1's in a byte

[munna_dude]

Hi all
how to count number of 1's in a byte.
please explain me about this.

any help it should be appreciable

[zacs7]

There are a few ways, perhaps the easiest is:

1. shift
2. AND
3. repeat CHAR_BITS times

[matsp]

If you want to do it OFTEN, and you KNOW that a byte is always 8 bits, you could use a table - most efficient is probably a table for 4 bits at a time. This makes it two lookups and one shift, instead of (say) 8 shifts.

Of course, a char or byte is not necessarily 8 bits - although hardware with other varieties is quite rare, it's worth considering if you want highly portable code.

--
Mats

[QuantumPete]

We actually ask this as an interview question. Assuming you have an 8 bit char, you can use a 256 element lookup table.

QuantumPete

[matsp]

We actually ask this as an interview question. Assuming you have an 8 bit char, you can use a 256 element lookup table.

QuantumPete

Yes, that would be the fastest method, but in some cases, using a bigger table will reduce the chances of hitting in the cache - a 16 entry table will fit in one or two cache-lines. [But if it's frequent enough, using a bigger table will be quicker].

--
Mats

[MK27]

We actually ask this as an interview question. Assuming you have an 8 bit char, you can use a 256 element lookup table.

QuantumPete

It's also one of the C examples used in the wikipedia entry for "lookup table", as is matsp's point about cacheing.

[foxman]

We actually ask this as an interview question. Assuming you have an 8 bit char, you can use a 256 element lookup table.

But then, the question becomes: how do you build such a table ?

[nonoob]

I guess at some point you need to shift a 1-bit mask through the integer like any naive algorithm would do. Unless you are intimating there may be a mathematical shortcut. Damn now I'll have to research it further. I love puzzles.

Oh, darn, it's already solved to death.
http://gurmeetsingh.wordpress.com/20...ting-routines/
and
http://en.wikipedia.org/wiki/Hamming_weight

[master5001]

Example:

union sub_optimal_solution
{
  struct
  {
    unsigned char bit0 : 1;
    unsigned char bit1 : 1;
    unsigned char bit2 : 1;
    unsigned char bit3 : 1;
    unsigned char bit4 : 1;
    unsigned char bit5 : 1;
    unsigned char bit6 : 1;
    unsigned char bit7 : 1;
  };

  unsigned char all;
};

/* The above uses some non-standard extentions that are safe with GCC and MSVC */
int bitCount(char x)
{
  union sub_optimal_solution y;

  y.all = x;

  return y.bit0 + y.bit1 + y.bit2 + y.bit3 + y.bit4 + y.bit5 + y.bit6 + y.bit7;
}

Is this a good way of doing this? Hells nah! Does it work? As long as your compiler can compile it.

[nonoob]

Yeah but wouldn't that be just as efficient (or not) as

return y.bit0 + y.bit1 + y.bit2 + y.bit3 + y.bit4 + y.bit5 + y.bit6 + y.bit7

with no questions asked.

[master5001]

Touche

[itCbitC]

What about the age old method of converting decimal to binary by repeated division as in

#include <stdio.h>

int main(void)
{
    unsigned char bc, rem;
    unsigned char quot = 123;
    printf("num of bits in %d ", quot);
    while (quot) {
        if ((rem = (quot % 2)) == 1)
            ++bc;
        quot /= 2;
    }
    printf ("is %d\n", bc);
}

[master5001]

Luckily any modern compiler would just automatically convert all of that to bit shifts and bitwise ANDs.

[itCbitC]

Luckily any modern compiler would just automatically convert all of that to bit shifts and bitwise ANDs.

Yes and the C bitwise operators would be lot faster as there's a 1-to-1 map between them and the machine code generated as those instructions are built into almost all micros.

#include <stdio.h>

int main(void)
{
    unsigned char bc, rem;
    unsigned char quot = 132;
    printf("num of bits in %d ", quot);
    while (quot) {
        if ((rem = (quot & 1)) == 1)
            ++bc;
        quot >>= 1;
    }
    printf ("is %d\n", bc);
}