15,399,959 members
1.00/5 (1 vote)
See more:
Question--->
Print a single base-10 integer that denotes the maximum number of consecutive's 1 in the binary representation of N.
Here, `N == (input given by the user)`

My approach-->
```#include <stdio.h>

int main(){
int n,count=0,max=0;
scanf("%d",&n);
while(n>0)
{
if(n%2==1)
count++;
else
{
if(count>max)
max=count;
count=0;
}
n/=2;
}
if(count>max)
max=count;
printf("%d",max);
return 0;
}```

What I have tried:

I know this code is already very optimized as It takes O(log n) time.
So,
Can anyone give suggestions to make this code shorter with the same (log n) complexity?
Someone told me to use bitwise operators but, I don't understand how?
Posted
Updated 17-Mar-22 11:59am

## Solution 3

Quote:
I know this code is already very optimized as It takes O(log n) time.

Indeed, but you take the 1 bit at the time approach. Your code runtime depend on position of leftmost bit set to 1.
Bitwise approach can lead to much more optimized code, because you can enable parallel operations which make an O(n) depending on size of longest run of 1's, no matter its position .
C++
```#include <stdio.h>

#include <stdio.h>

int main(){
int n,max=0,Tmp;
scanf("%d",&n);
Tmp= n;
while(n>0)
{
max++;
Tmp >>= 1;
n &= Tmp;
}
printf("%d",max);
return 0;
}```

To get this algorithm, you need to master Boolean algebra and bitwise operations on processors.
If you want to follow operations, I recommend to add prints of binary values of variable.
This technique can be assimilated to SIMD instructions of the poor.
Single instruction, multiple data - Wikipedia[^]
v3
CPallini 18-Mar-22 3:19am

Beautiful, my 5.
Patrice T 18-Mar-22 3:47am

Thank you

## Solution 1

The bitwise operators you want to look at are AND: & and SHIFT RIGHT: >>
If you AND a number with 1, you get either 0 or 1 depending on eth status of the bottom bit.
If you SHIFT RIGHT a number, you move each bit down: 010101 becomes 001010, then 000101, ...
So your "if and then divide" that is the whole of your loop body could be replaced with two bitwise instructions with no testing or other flow control necessary ...

Have a think about it, you'll see what I mean!

[EDIT]
No, that's not quite right - you need the consecutive 1s, not the total count. I missed that.
You'd need a test, but it could be a little simpler.
[EDIT]
v2

## Solution 2

`if(n & 0x01)` will be `true` if n is odd (ends in a "1" bit).

And `n >>= 1` will shift `n` right by one bit, dropping off the low-order bit so that you can check the next one.

The rest is up to you.

## Solution 4

You can take at least two approaches to the bitwise algorithm : either shift the data or shift the mask. Here is an example that shifts the mask :
C++
```typedef unsigned int  UINT;
typedef unsigned char UCHAR;

void UnpackBits( UINT value, UCHAR bits[] )
{
const int bitCount = 8 * sizeof( UINT );  // eight bits per byte
for( int n = 0; n < bitCount; ++n )
{
bits[ n ] = 1;
else
bits[ n ] = 0;
}
}```
When the loop completes you will have an array of 1s and 0s corresponding to each bit of the integer. Bit 0, the least significant one, will be first in the array.
Patrice T 17-Mar-22 21:18pm

Not sure your code is related to the question.
Wouldn't it be easier to use a bit field array ?
Rick York 18-Mar-22 10:53am

Performance-wise that is the worst possible option. I avoid bit fields when ever possible.

The question is about determining patterns in the bits. This shows how one can find out what the bits are.
Patrice T 18-Mar-22 11:35am

Yes, when one start to do convertions on bits, it turn to nightmare rather quickly.
But playing directly with bits, it is fast.
Look at solution 3, it should be optimal.
Rick York 18-Mar-22 15:35pm

Did you read what I wrote? I will repeat it : "You can take at least two approaches to the bitwise algorithm : either shift the data or shift the mask." You shifted the data, this solution shifts the mask. This was solely to present another option.