Click here to Skip to main content
15,399,959 members
Please Sign up or sign in to vote.
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

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
Comments
CPallini 18-Mar-22 3:19am
   
Beautiful, my 5.
Patrice T 18-Mar-22 3:47am
   
Thank you
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
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.
   
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
    UINT mask = 1;
    for( int n = 0; n < bitCount; ++n )
    {
        if( mask & value )
            bits[ n ] = 1;
        else
            bits[ n ] = 0;
        mask <<= 1;           // shift mask one slot to the left
    }
}
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.
   
Comments
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.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900