Count maximum contiguous set bits in an integer .

[Vish]

Hi All

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.
111000111110000 101010111111 : 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))).

Here is the program:

int main()
{
int count=0,n,i,tem p=0;
printf("Enter the number \n");

/*Numer is in decimal for calculation we have to use binary
representation for calculation*/

scanf("%d",&n);

for (i=0;i<(8*sizeo f(int));i++)
{
if((n&1)==1)
count++;
else
{
if (temp<count)
temp=count;
count=0;
}
n= n>>1;
}
if (temp==0)
printf("count of contiguous bits= %d\n",count);
else
printf("count of contiguous bits = %d\n",temp);

return 0;
}

[websnarf@gmail.com]

Re: Count maximum contiguous set bits in an integer .

Vish wrote:[color=blue]
> 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.
> 111000111110000 101010111111 : 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))).[/color]

How about a 5 liner?

int longest1BitsCou nt (unsigned long l) {
int i;
for (i=0; l; i++) l &= l + l;
return i;
}

Like any other program, I have no idea what this does on a 1s
complement machine (and don't really care).

---
Paul Hsieh

http://www.pobox.com/~qed/

http://bstring.sf.net/

[Lawrence Kirby]

Re: Count maximum contiguous set bits in an integer .

On Fri, 29 Apr 2005 04:05:04 -0700, websnarf wrote:
[color=blue]
> Vish wrote:[color=green]
>> 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.
>> 111000111110000 101010111111 : 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))).[/color]
>
> How about a 5 liner?
>
> int longest1BitsCou nt (unsigned long l) {
> int i;
> for (i=0; l; i++) l &= l + l;
> return i;
> }[/color]

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?
[color=blue]
> Like any other program, I have no idea what this does on a 1s complement
> machine (and don't really care).[/color]

Since l has an unsigned type what signed integer representation an
implementation uses has no relevance to it.

Lawrence

[websnarf@gmail.com]

Re: Count maximum contiguous set bits in an integer .

Lawrence Kirby wrote:[color=blue]
> On Fri, 29 Apr 2005 04:05:04 -0700, websnarf wrote:
>[color=green]
> > Vish wrote:[color=darkred]
> >> 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.
> >> 111000111110000 101010111111 : 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))).[/color]
> >
> > How about a 5 liner?
> >
> > int longest1BitsCou nt (unsigned long l) {
> > int i;
> > for (i=0; l; i++) l &= l + l;
> > return i;
> > }[/color]
>
> 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?[/color]

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/