1313. The AND of Every Number From l to r
For each of q queries l r, print the bitwise AND of every INTEGER from l
to r inclusive. These are the numbers themselves, not entries of an array.
5 7 -> 4 5 & 6 & 7
12 15 -> 12
8 15 -> 8
1 1 -> 1
1023 1024 -> 0
## What most people try first
The loop from l to r. The range can hold 10^18 numbers, so it cannot
finish. #1261 does the XOR version of this and finds a closed form from a
period-4 pattern; AND has no such pattern, and needs a different observation.
## A bit survives only if it is 1 in every number of the range
That is just #1307's reading of AND, applied here. So ask, for a bit position
b, whether every number from l to r has bit b set.
The answer is a strong constraint. If l and r DIFFER at position b, then
somewhere in between the bit must have been 0, so it cannot survive. And if
l and r differ at any position ABOVE b, then the range spans a carry
through position b, which forces a 0 there too: crossing a power of two larger
than 2^b resets every bit below it.
So a bit survives only if l and r agree at that position AND at every
position above it. In other words:
AND(l..r) = the common binary PREFIX of l and r, with zeros below it
## Computing the common prefix
Shift both values right together until they are equal, counting the shifts, then shift back:
shift = 0
while l != r:
l >>= 1
r >>= 1
shift += 1
answer = l << shift
At most 60 iterations. When l == r at the start the loop does not run and the
answer is l, which is correct since the range holds one number.
Checking it on 12 15: 1100 and 1111 differ, shift to 110 and 111,
differ, shift to 11 and 11, equal after 2 shifts, so the answer is
11 << 2 = 1100 = 12. And on 8 15: 1000 and 1111 reduce to 1 and 1
after 3 shifts, giving 1 << 3 = 8.
## The consequence worth remembering
If r >= 2 * l then l and r have different bit lengths, so they share no
prefix at all and the answer is 0. That is why 1023 1024 is 0: the range
crosses a power of two and nothing survives. Any range spanning a power of two
larger than its lower end answers 0.
## Cost
O(60) per query, so O(q) overall, against a loop that cannot run.
## Width
Values reach 10^18, below 2^60, so everything fits in a signed 64-bit
integer, whose limit is 9223372036854775807. A signed 32-bit integer, limit
2147483647, cannot hold the inputs: truncating 10^18 to 32 bits gives
-1486618624, and a 32-bit build answers -1486618624 on the maximum test
where the correct answer is 1000000000000000000.
In JavaScript >> and << coerce to signed 32 bits, and the values also pass
2^53 = 9007199254740992, so the reference uses BigInt. #1314 is the OR
version of this problem and uses the same prefix observation from the other
side.
Constraints - `1 ≤ q ≤ 100000` - `0 ≤ l ≤ r ≤ 1000000000000000000`
Input
The first line contains an integer q.
Each of the next q lines contains two integers l and r, separated by a space.
Output
For each query print one integer on its own line: the bitwise AND of all integers from l to r inclusive.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.