Can this code in C become shorter, with the same time complexity?

Question

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 17-Mar-22 6:40am

Aniket Mani

Updated 17-Mar-22 11:59am

Add a Solution

4 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Patrice T · Accepted Answer · 2022-03-17T08:45:00

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[^]

OriginalGriff · Accepted Answer · 2022-03-17T06:49:00

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]

Greg Utas · Accepted Answer · 2022-03-17T06:49:00

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.

Posted 17-Mar-22 6:49am

Greg Utas

Rick York · Accepted Answer · 2022-03-17T11:59:00

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

Posted 17-Mar-22 11:59am

Rick York

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.

Can this code in C become shorter, with the same time complexity?

4 solutions

Solution 3

Solution 1

Solution 2

Solution 4

Add your solution here

Preview 0