Thread: How many bits are '1' in an integer variable?

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!!

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.

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.

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?

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.

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