Hello
I have this code :
Is there any way to write the function without using a loop?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; }
Yes. For example, you could use a lookup table.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
lookup table? I have never use this before ...
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.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
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 :/
He means you only need 8 lines of this:
You will have to shift ch to check the proper bit in each line, but you can do that.Code:c += ch & 1;
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; }
Last edited by Mr.Lnx; 07-13-2014 at 08:06 AM.
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.
Last edited by grumpy; 07-13-2014 at 08:11 AM.
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.
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
as a simple mind trick
deliberatly leave the explanation outCode: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; }
All problems in computer science can be solved by another level of indirection,
except for the problem of too many layers of indirection.
– David J. Wheeler
Shouldn't
beCode:val = ((val &0xF0) >> 4 ) + (val & 0x0f);
?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.
-
Last edited by megafiddle; 07-14-2014 at 06:42 AM.
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:
RonCode:unsigned char count[256] = {0,1,1,2,1,2,2,3,1,2...6,7};
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.
