BITWISE AND(&) for Range of Numbers

general
,
1

Given two numbers L & R , Find Bitwise AND of all numbers lying between L and R inclusive
Constraints 1<= L,R <= (2^32).

long long step = 1;
 while(L!=R)
    {
        L/=2; R/=2; step*=2;
    }
    printf("%lld\n",L*step);

Can anybody help me with the explanation or logic behind the above code?

2 Likes
2

Hi naveen,

in this question we will have to play with bits :

now think in binary

let L and R are not equal means we will find at least one 0(zero) in LSB(least significant bit) of numbers from L to R and if there second last bits are 1 and difference between them is >1 means we will find at least one zero from L to R for second bit.

eg.

0000

0001

0010

0011

0100

0101

let L=2 and R=3 so there second bit is 1 and difference is not greater than 1 so in & operation we will not have zero at this position which is our objective. if we have 0 in any one of L or R then no need to do anything for that position.

if third bit is 1 (both L and R) then difference must be >3 to achieve zero at that position.
so the formula comes out for i(th) bit difference must be greater than or equal to 2^(i-1).

in this problem efficient algo is used But concept is same

in step variable they are storing how many of bits from LSB are zero until L!=R in place of step you can use a counter variable © and count how many times loop run and then left shift ( L<< c or R<< c) to get answer.

so lets iterate with L = 110010110 and R = 110011101

in first iteration L and R are not equal means there is at least one zero in LSB of L to R. and multiply step by two so step = 10 means last bit is off (zero) and now right shift both(L,R) to remove LSB because we have done with LSB.

in second iteration (same as above) we have at least one zero from L to R so multiply step by two step = 100 second bit is also off. and right shift both

in third iteration L is not equal to R but there LSB is same means at least one of there bit except LSB is differ ( so if any one of more significant bit differ means LSB will definitely flip at least once ) so our third bit is also zero hence multiply step = 1000.

same for fourth bit and after fourth bit we have L==R means non of bit differ from each other so multiply ( L or R ) with step to get answer or left shift L << 4 to get answer.

it was explanation of your query but for more efficiency iterate form MSB to LSB and if bits are same then oK but when first time bits differ then make 0(zero) all of bits from that position to LSB because if more signi. bit will differ then less signi. bit will definitely differ.

i know you got that :slight_smile:

1 Like
3

There is a O(1) solution as well. :slight_smile:

  1. XOR a and b.
  2. Find its next power of 2.
  3. Subtract 1.
  4. Flip its bits and AND with either a or b.

a & ~(nextpowerof2(a^b)-1)