| Andy Champ 2006-11-05, 6:58 pm |
| Pascal Bourguignon wrote:
> "karthikbg" <karthik.balaguru@lntinfotech.com> writes:
>
>
>
> The most efficient way is to use google: bit count
>
Just out of interest I did. The third hit said "A common problem asked
in job interviews is to count the number of bits that are on in an
unsigned integer". Hmmm... And in (mumble) years in software I can't
remember having to do it!
However I would say I am lacking information to answer your question.
If the size of the value is small, and you want to do it often, use a
lookup table. For example, on a 4-bit integer, the table would read
{0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4}.
On a 32-bit integer, the table would be kind of big and clumsy (4Gb!).
On a file, out of the question. So I think in general I'd make a table,
and chop my original value into pieces that match the table. But it'll
depend on whether size or performance really matter - if size is really
important, genuinely count them; if performance really matters, you
want a really big table.
Oh yes, if you really want speed, you might want to hand-craft
something. For example, use the Intel assembler instruction LODSB to
fetch the next byte from your value. Or maybe toss it at your GPU.
Andy
|