# number of 1's in a byte

This is a discussion on number of 1's in a byte within the C Programming forums, part of the General Programming Boards category; Hi all how to count number of 1's in a byte. please explain me about this. any help it should ...

1. ## number of 1's in a byte

Hi all
how to count number of 1's in a byte.

any help it should be appreciable

2. There are a few ways, perhaps the easiest is:

1. shift
2. AND
3. repeat CHAR_BITS times

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

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

QuantumPete

5. Originally Posted by 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
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

6. Originally Posted by 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
It's also one of the C examples used in the wikipedia entry for "lookup table", as is matsp's point about cacheing.

7. Originally Posted by QuantumPete
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 ?

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

9. Example:
Code:
```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.

10. Yeah but wouldn't that be just as efficient (or not) as
Code:
`return y.bit0 + y.bit1 + y.bit2 + y.bit3 + y.bit4 + y.bit5 + y.bit6 + y.bit7`

11. Touche

12. What about the age old method of converting decimal to binary by repeated division as in
Code:
```#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);
}```

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

14. Originally Posted by master5001
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.
Code:
```#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);
}```