CODEWITHSUNDEEP
c++bitwise-operators
user3481652
user3481652

Reputation: 69

What does this bitwise expression do?

n & (n>>1)

Where can I use the above expression? I was doing this problem and I saw this solution to problem where the expression is used.

Problem-

You are given an integer n find its next greater or equal number whose    
binary representation must not contain consecutive ones.

code-

main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
    scanf("%d",&n);
    while((n&(n>>1)))
    {
        n++;
    }
    printf("%d\n",n);
}
}

Upvotes: 1

Views: 133

Answers (2)

smali
smali

Reputation: 4805

It is first shift the bits in variable n to right

>> - Bitwise shift right

Then perform the and operations with the shifted bit..

& - Bitwise and Operation.

here the complete operation is happening like this

consider int n=6

so its binary equivalent will be 110 .. and you have to find out next greater than or equal number whose binary equivalent should not contain two consecutive one's in it.

so you that no will be 8 as its binary equivalent is 1000

so if you perform

(n>>1) result will 011

if you do and operation the 

011
110

result will be 

010

now trace your answer code

main()
{
 int t,n;
 scanf("%d",&t);
 while(t--)
 {
    scanf("%d",&n);
    while((n&(n>>1)))
    {
        n++;
    }
    printf("%d\n",n);
 }
}

Upvotes: 1

Axel
Axel

Reputation: 14169

It checks for consecutive ones in n. It does a bitwise AND operation on n and n shifted one bit to the right. If the binary representation of n has at least two adjacent ones, you will get something like this:

n    :       00001100 
n>>1 :       00000110
---------------------
n & (n>>1) : 00000100

Compare this to the original assignment:

You are given an integer n find its next greater or equal number whose binary representation must not contain consecutive ones.

Upvotes: 10

Related Questions