# How many bits are '1' in an integer variable?

This is a discussion on How many bits are '1' in an integer variable? within the C Programming forums, part of the General Programming Boards category; Originally Posted by cuthbert The fastest way I found is using lookup table. For integer, 4 bytes long, it takes ...

1. Originally Posted by cuthbert
The fastest way I found is using lookup table. For integer, 4 bytes long, it takes 4 additional operators only.
I am not 100% sure what you mean by that, did you look at the object code and count the instructions?
The actually run time is probably not directly related to the number of instruction, although it is a
good guide. Some instructions take longer to execute than others, depending on various factors. The best way to determine the actually would be to time a test run of several thousands runs of the programs code? I might try that for a laugh - I'm bored!!

2. Some compilers allow you to view the assembly output.

Quzah.

3. Originally Posted by citizen
> You could but it would take 8 times longer to complete (at least).
Performance isn't always a problem, and this is beyond the scope of the original question.
The OP said:-
"I am trying to find a more efficient way to count "How many bits are'1' in an integer variable?"."

So it depends what he means by efficient, if he means efficient in run time then it is in scope, in my opinion. He didn't specify exactly what he meant but he did mention opcode (IIRC) which could mean the number of opcodes in the program or the number executed, again he didn't
specify.

4. Except that you also said the following:
I guess the fastest way would be really huge look up table, for a 32 bit int you would need
4 gigabites+ of memory though.
For a 64 bit int well, you might need a loan to buy the memory
This thread wasn't even about integers that huge until you brought it up. But by all means, lets ignore an entire data structure because you think it doesn't work.

The program might take a while to load but once loaded it would run like lightening!!
Here you refute your own argument because many programs take a while to load and then run smoothly. That's exactly what the op wants. Computers happen to be fast at math most of the time so it's time that probably won't be missed.

5. Funny, Cuthbert asked this same question in comp.lang.c. Pete as usual posted a nice solution.

6. I still proclaim itoa() the fastest... non portable way

7. Fastest how? In developement time, because you don't have to type anything?
There's no way it's going to beat a lookup table, even if you do have to do it a byte at a time.

Quzah.

8. hmm... yes. You are right. I was only looking at the problem isolated from its possible uses, not thinking it could be called inumerous times. A lookup table would be a burden in that case.

9. > for ( i = 0; i < sizeof(int)*8 ; i++ )
Use the value of CHAR_BIT, not 8

10. Originally Posted by Mario F.
A non-portable way is to use itoa() if your compiler supports it, with a radix of 2. This will return a C-style string you can then count for 1s.

A portable way involves the use of recursion as seen here http://www.engin.umd.umich.edu/CIS/c...pp/binary.html, changing it where appropriate to count 1s.

Both options are faster than what you are doing.

EDIT: Well... swoopy's faster no doubt
I see a call to integer division in that code, are you saying that integer division (the mod operator) is faster than a shift and a bitwise AND like the OP's code ?

I don't see how the recursive one would be any faster, anyone care to test it?

11. Did you look closely at it?

You don't have to iterate sizeof(int)*8 times to output the result unless your int is that big.

12. I know of a way to do it in ASM that only iterates 1 time for each bit in the integer but I don't know if it can be done in C aside from using inline assembly; it involves the use of the ROL (or ROR) operation plus the JC operation.

13. Originally Posted by MacNilly
I know of a way to do it in ASM that only iterates 1 time for each bit in the integer but I don't know if it can be done in C aside from using inline assembly; it involves the use of the ROL (or ROR) operation plus the JC operation.

The C >> and << commands are the equivilant of ROR and ROL

14. Originally Posted by esbo
The C >> and << commands are the equivilant of ROR and ROL
No. The << and >> operators are more equivalent to SHL and SHR. The difference being ROR and ROL slap the shifted-off bit back on the other end, kind of like a conveyer belt.

I wish you'd stop spreading bad information. If you don't know the answer, don't make it seem like you do.

15. > The C >> and << commands are the equivilant of ROR and ROL
No they are not.
ROL would (in 8 bits) turn 0x80 into 0x01, where the C operator would turn it into 0
<< and >> propagate zeros (mostly), not the bits which fall off the end.

ASL and ASR or SAL and SAR are more likely choices.

Page 3 of 4 First 1234 Last