# Thread: Counting set bits in a character.

1. ## Counting set bits in a character.

Hello I have this code :

Code:
```

#include <stdio.h>

int countSetBits(unsigned char ch)
{
unsigned int c;

for( c = 0; ch; ch >>=1)
c += ch & 1;

return c;
}

int main(void)
{

unsigned char ch;

printf("Enter a character: ");
scanf(" %c" , &ch);

printf(" The number of set bits (1) in character %c is : %d \n" , ch , countSetBits(ch) );

return 0;
}```
Is there any way to write the function without using a loop? 2. Yes. For example, you could use a lookup table. 3. lookup table? I have never use this before ... 4. Well, in its simplest form, given an 8-bit byte, you could have an array of 256 integers. The index of each element corresponds to a possible value of the character, and the value corresponds to the number of set bits. So, to get the count of set bits of the character, you simply access the array by index, i.e., by the value of the character.

There are ways to compact this, and then there are yet other ways that may be harder to understand but require less space and may be as efficient. 5. An alternate way is to unroll the loop. 6. Originally Posted by grumpy An alternate way is to unroll the loop.
Unroll the loop? what do you mean by that? :/

well I am good when I have a code to read and understand but I am not so good when I have to write a code from the beginning :/ 7. He means you only need 8 lines of this:
Code:
`c += ch & 1;`
You will have to shift ch to check the proper bit in each line, but you can do that. 8. But is this efficient? I think it is ungly and not readable.

Code:
```
int countSetBits(unsigned char ch)
{
unsigned int c=0;

//for( c = 0; ch; ch >>=1)
c += ch & 1;  ch >>=1;
c += ch & 1;  ch >>=1;
c += ch & 1;  ch >>=1;
c += ch & 1;  ch >>=1;
c += ch & 1;  ch >>=1;
c += ch & 1;  ch >>=1;
c += ch & 1;  ch >>=1;
c += ch & 1;  ch >>=1;

return c;
}``` 9. Originally Posted by Mr.Lnx But is this efficient? I think it is ungly and not readable.
In principle, it's the same efficiency or marginally better, since there doesn't have to be a branch (check a condition and jump to some place in code). It would involve more instructions written to an executable file (i.e. a bigger executable).

Yes, doing it with a loop is often the less ugly and more readable solution. But you asked if it was possible to do it without the loop - hence effectively asked for the more ugly and less readable options. You can't have your cake and eat it too. 10. It is not any less efficient. The simplest thing I can think of requires a loop as well, so you will probably be stuck with a lookup table if you must do it differently. 11. Yes you are right. I used the term efficient in terms of readability and beauty of code. It has nothing to do with the classic term because of condition and jumping as you said. Maybe it is completely wrong the fact that I used this term. Anyway thank you  12. as a simple mind trick
Code:
```unsigned char count_bits(unsigned char val)
{
val = ((val &0xAA) >> 1 ) + (val & 0x55);
val = ((val &0xCC) >> 2 ) + (val & 0x33);
val = ((val &0xF0) >> 4 ) + (val & 0x0f);
return val;
}```
deliberatly leave the explanation out 13. Shouldn't

Code:
`val = ((val &0xF0) >> 4 ) + (val & 0x0f);`
be

Code:
`val = ((val &0x07) >> 4 ) + (val & 0x07);`
?

Ok, I see that bits 3 and 7 would have already been forced to zero at that point.
0x70 and 0x07 makes ihe operation a little bit clearer.

- 14. Hello, I am a new user. This is my first post.

A 'cooler' solution would be use a lookup table, as suggested by laserlight, consisting of an array of 256 integers containing the count of ones in each possible byte 0 to 255. Then you just index into the array, with the byte in question, to get the count. Very fast. To start:

Code:
`unsigned char count = {0,1,1,2,1,2,2,3,1,2...6,7};`
Ron 15. Originally Posted by BasicPoke Hello, I am a new user. This is my first post.

A 'cooler' solution would be use a lookup table, as suggested by laserlight, consisting of an array of 256 integers containing the count of ones in each possible byte 0 to 255. Then you just index into the array, with the byte in question, to get the count. Very fast.
Don't confuse fewer lines of C code with fast. Worst case (the array isn't in cache) this will be much slower than a loop or some of the other tricks mentioned above. Popular pages Recent additions 