AND Across a Range

Medium

You are given two integers low and high with low ≤ high. Compute the bitwise AND (&) of every integer from low to high inclusive. Looping over every number may be too slow: the range can span billions of values.

Example 1

low=12, high=15 → 12

In binary 12 = 1100, 13 = 1101, 14 = 1110, 15 = 1111. Only the two top bits are shared by all of them: 1100 = 12.

Example 2

low=7, high=8 → 0

7 = 0111 and 8 = 1000 share no set bits at all.

Example 3

low=21, high=21 → 21

The range holds a single number, which is the answer.

Constraints

0 ≤ low ≤ high ≤ 2³¹ − 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation

Similar problems

Division Without Dividing Medium Every Topping Combo Medium Mirrored One-Bit Codes Medium All Distinct Card Hands Medium The Odd One Among Triples Medium

Input

low=12, high=15

Expected

Run checks the first 3 tests in your browser. Submit checks all 100 tests on the server, hidden ones included.