John Doe - 1 year ago 54

Java Question

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 one line per test case with the required bitwise AND.

3

12 15

2 3

8 13

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();

}

}

Answer Source

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