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.
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))).

Here is the program:

int main()
{
int count=0,n,i,temp=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*sizeof(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]

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;
}

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]

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

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

Lawrence

[websnarf]

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/