Bitwise AND of All Numbers in a Range

Given two non-negative integers M and N with M <= N, compute the bitwise AND of every integer in the inclusive range [M, N] - that is, M AND (M+1) AND (M+2) AND ... AND N. The range can be extremely wide (up to about 2 billion numbers), so your solution must not iterate over every value in it. Print the resulting value.

Input: A single line containing two space-separated integers, M and N. Output: A single line containing the bitwise AND of all integers from M to N inclusive.

0 <= M <= N <= 2^31 - 1

This 'find the common prefix by shifting both numbers together' technique is specifically what makes an otherwise range-size-dependent problem run in time depending only on the NUMBER OF BITS, not the range's magnitude - a valuable insight whenever a range could be astronomically large.

Compute the bitwise AND of every integer in a range [M, N], without checking every number individually. Brute force: AND every single number in the range together directly, one at a time - this costs O(N-M), which can be up to about 2 billion operations, far too slow. Optimised: Since ANDing a whole range collapses any bit that varies ANYWHERE within it down to 0, only the bits that are IDENTICAL across the entire range (the shared binary prefix of M and N) can survive - finding this shared prefix via repeated right-shifting takes only O(log(max value)) steps, regardless of how huge the range itself is.

1. Find the common binary PREFIX shared by M and N - any bit that ever differs somewhere across the range must eventually become 0 in the final AND (since some number in the range has that bit as 0). 2. Repeatedly right-shift BOTH M and N together, counting the shifts, until they become EQUAL - that equal value is exactly the shared prefix. 3. The answer is that common value shifted back LEFT by the number of shifts counted.

Time: O(log(max value)) - at most about 31 shifts for 32-bit integers, completely independent of the range's actual size. Space: O(1) - just a shift counter and the two shifting values.

M equal to N means the answer is just M itself; a range that spans a power-of-two boundary (e.g. 0 to 2^31 - 1) always collapses to 0.

Be ready to explain WHY any bit that differs anywhere in the range must become 0 - since the range includes EVERY integer between M and N, if a bit ever flips from 1 to 0 somewhere in that span, some number in the range definitely has it as 0, and ANDing with that number clears it.