Bitwise AND of Numbers Range

Medium#201bit by bit

You get two numbers left ≤ right. Return the bitwise AND of every integer from left to right, both ends included. The range can hold billions of numbers, so going through them is too slow. Our example: left = 26, right = 30 — the answer is 24.

201 Bitwise AND of Numbers RangeWalkthrough · 1×

Example: left = 26, right = 30. Every number of the range is drawn in binary, but the run reads only left and right.

left2611010= 26271101128111002911101right3011110= 30AND—
a 1 bita 0 bitthe highest bit where left and right differa dropped bita 0 in a dropped column: it makes that bit 0 in the ANDthe shared start; the answer

left = 26 = 11010, right = 30 = 11110. Nothing is shifted yet

01/15
restart · back · play · step
Speed
1function rangeBitwiseAnd(left, right):
2 shift = 0
3 while left != right:
4 left = left >> 1
5 right = right >> 1
6 shift = shift + 1
7 return left << shift
state
left
26 = 11010
right
30 = 11110
shift
0
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Counting from left up to right, a number changes its low bits before its high ones. Below the highest bit where left and right differ, some number in between ends in all zeros (28 = 11100 here), so every such bit is 0 in the AND.
  2. Above that bit, left and right agree, and every number between them has the same bits there, so the AND keeps them. Shifting both right until they are equal finds exactly that shared start.
  3. Shifting back by shift puts the start in its place and fills the dropped columns with zeros. The numbers between left and right are never read, so the range may be as long as you like.

Complexity

Time O(log right): one shift per bit, at most 31 on LeetCode. Memory O(1): three numbers.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.