All problems

Bitwise AND of Numbers Range

Medium · bit manipulation

You are given two non-negative integers left and right, with left <= right.

Take every whole number from left to right, with both ends included, and combine them all with the bitwise AND operation. The result has a 1 in a binary position only if every one of those numbers has a 1 in that position.

Return that result. If left and right are equal, the range holds a single number and the answer is that number.

Examples

Example 1

Input: left = 5, right = 7

Output: 4

In binary 5 = 101, 6 = 110 and 7 = 111. Only the leftmost position is 1 in all three, which is 100 = 4.

Example 2

Input: left = 12, right = 15

Output: 12

12 = 1100, 13 = 1101, 14 = 1110 and 15 = 1111. The two leftmost positions are 1 in all four, which is 1100 = 12.

Example 3

Input: left = 9, right = 16

Output: 0

The range contains 15 = 01111 and 16 = 10000, which share no 1 in any position, so the result is 0.

Constraints