Bitwise AND of Numbers Range

Средняя№201по битам

Даны два числа left ≤ right. Нужно вернуть побитовое AND всех целых от left до right, оба конца включительно. В диапазоне могут быть миллиарды чисел, поэтому перебирать их слишком долго. Наш пример: left = 26, right = 30 — ответ 24.

201 Bitwise AND of Numbers RangeРазбор · 1×

Пример: left = 26, right = 30. Все числа диапазона нарисованы в двоичной записи, но прогон читает только left и right.

left2611010= 26271101128111002911101right3011110= 30AND—
бит 1бит 0старший бит, где left и right различаютсяотброшенный бит0 в отброшенном столбце: из-за него этот бит в AND равен 0общее начало; ответ

left = 26 = 11010, right = 30 = 11110. Пока ничего не сдвинуто

01/15
сначала · назад · пуск · шаг
Скорость
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
состояние
left
26 = 11010
right
30 = 11110
shift
0
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Когда считаешь от left до right, у числа сначала меняются младшие биты, потом старшие. Ниже старшего бита, где left и right различаются, какое-то число между ними кончается одними нулями (здесь 28 = 11100), поэтому все такие биты в AND равны 0.
  2. Выше этого бита left и right совпадают, и у всех чисел между ними там те же биты, поэтому AND их сохраняет. Сдвиг обоих вправо, пока они не сравняются, находит ровно это общее начало.
  3. Сдвиг обратно на shift ставит начало на место и заполняет отброшенные столбцы нулями. Числа между left и right не читаются, поэтому диапазон может быть сколь угодно длинным.

Сложность

Время O(log right): по сдвигу на бит, на LeetCode не больше 31. Память O(1): три числа.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.