John Doe John Doe - 6 months ago 8
Java Question

Bit AND amongst all natural numbers lying between A and B (both inclusive)

I came across this problem on a competitive problem site.
Here is the problem:-

Problem Statement

You will be given two integers A and B. You are required to compute the bitwise AND amongst all natural numbers lying between A and B (both inclusive).

Fix the code in the editor so that it solves the problem above. You need to complete the missing line marked by "~~Fill this line". Don't modify or insert any other lines, otherwise you will get a wrong answer even if your code is correct.

Input Format

First line of the input contains T, the number of testcases to follow. Each testcase in a newline contains A and B separated by a single space.

Constraints:

1<=T<=200
0≤A≤B<2^32


Output Format
Output one line per test case with the required bitwise AND.

Sample Input

3

12 15

2 3

8 13

Sample Output

12

2

8

Here is the code wherein we have to fill the missing line :

import java.math.BigInteger;
import java.util.Scanner;

public class Magic4 {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

int T = scanner.nextInt();

for (int t = 0; t < T; t++) {
long l = scanner.nextLong();
long r = scanner.nextLong();
long res = 0;
for (long i = 0; i < 32; i++) {// I can make out that we are dealing with 32 bit numbers hence we are setting the condition as i < 32, but after that the proceedings in the loop are vague.
if ((r - l + 1 == 1))
if(l%2==1)
~~Fill this line~~
l >>= 1; r >>= 1;
}
System.out.println(res);
}

scanner.close();
}
}


Problem I just could not solve it, i.e filling with the correct line even after spending some time. I can make out that we are dealing with 32 bit numbers hence we are setting the condition as i < 32, but after that the proceedings in the loop are vague. If you can make out something do let me know.

Answer
res = res | (1 << i);

Each iteration of the loop tests if the 32-i left-most bits of the two numbers (A and B, or l and r in the code) are equal to each other. If they are, the result of bit-wise AND of all the numbers between A and B must contain 1 for each of the 32-i bits of A (or B) that contain 1.

So if r - l + 1 == 1 (i.e. r==l) and l%2==1, the i'th bit of the result must be 1.