Re: Count maximum contiguous set bits in an integer .

Lawrence Kirby wrote:
> On Fri, 29 Apr 2005 04:05:04 -0700, websnarf wrote:
>
> > Vish wrote:
> >> I have written a program to count the maximum contiguous set bits
> >> in an integer.
> >> Like if my binary representation of integer is :
> >> 1100111 : then output should be 3.
> >> 111000111110000101010111111 : then output should be 6.
> >>
> >> I am including the snippet below.
> >> How can I optimize this code and also is there a one liner to
> >> implement the same.
> >> (Like for power of 2 we have got (number & (number -1))).
> >
> > How about a 5 liner?
> >
> > int longest1BitsCount (unsigned long l) {
> > int i;
> > for (i=0; l; i++) l &= l + l;
> > return i;
> > }
>
> Clever piece of code. was it intended to be mildly obfuscated i.e.
> using i and l which can look very similar, and using l+l instead
> of the clearer l<<1?

Shifts are slow on the Pentium 4 (and on Intel CPUs in general, versus
say an add, or how fast they are on AMD CPUs). It actually usually
doesn't matter, but I just default to the fastest path by instinct.

---
Paul Hsieh
http://www.pobox.com/~qed
http://bstring.sf.net/

.

Relevant Pages