Count maximum contiguous set bits in an integer .

V

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

websnarf

Vish said:
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).
 
W

websnarf

Lawrence said:
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.
 
L

Lawrence Kirby

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,983
Messages
2,570,188
Members
46,755
Latest member
HudsonP082

Latest Threads

Top