position and number of 1's in an integer

[junky_fellow]

Can anyone suggest some efficient way to find the
number of 1's as well as their position in a 32 bit integer ?

 

[Allan Bruce]

Can anyone suggest some efficient way to find the
number of 1's as well as their position in a 32 bit integer ?

1)you need to look at specifying a value with bit e.g. 0x1
2)you will need to use the bit shifting operators << or >>
3)you will need to use logical operators to determine if bits are set e.g. &

these plus a for loop will give you your answer!

Allan

 

[Eric Sosman]

Can anyone suggest some efficient way to find the
number of 1's as well as their position in a 32 bit integer ?

Counting the 1-bits is easy enough. Among the several
approaches are loops with masks and shifts, table-based
methods, "horizontal addition," and hybrids of these. Take
your pick.

As for "their position" -- well, it seems to me the
original 32-bit integer is a pretty efficient expression
of the positions of the 1-bits. What other expression did
you have in mind?

You may also be interested in Sean Eron Anderson's
collection of "Bit Twiddling Hacks"

http://graphics.stanford.edu/~seander/bithacks.html

Be warned that some of the tricks described there are not
entirely portable.

 

[puzzlecracker]

http://graphics.stanford.edu/~seander/bithacks.html

This is amazing!

 

[Richard Bos]

This is amazing!

Yes, it is. Amazingly non-portable, amazingly undependable, amazingly
unlikely to be more efficient than normal, legible code on all systems,
amazingly likely to have already been adopted by the implementation's
optimiser where appropriate, amazingly likely to be used by amateur
programmers to slow down their program and make it unmaintainable where
inappropriate.

In short, sane programmers do not use such ugly hacks unless absolutely
necessary.

Richard

 

[uekstrom]

I use this function to count bits in a 32 bit int on both little and
big endian platforms. It's fast, at least on pentium&co. It's written
in such a way that you can easily convert it to a macro if you like.

Ulf Ekström

/* (C) Donald W. Gillies, 1992. All rights reserved. You may reuse
this bitcount() function anywhere you please as long as you retain
this Copyright Notice. */
int bitcount(unsigned int n)
{
register unsigned int tmp;
return (tmp = (n) - (((n) >> 1) & 033333333333) - (((n) >> 2) &
011111111111),
tmp = ((tmp + (tmp >> 3)) & 030707070707),
tmp = (tmp + (tmp >> 6)),
tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077);
}