Reverse Bits

Лёгкая№190по битам

Дано беззнаковое целое фиксированной ширины — на LeetCode 32 бита. Нужно записать его биты в обратном порядке, младший первым, и вернуть получившееся число; нули в старших разрядах тоже считаются. Чтобы нарисовать каждый бит, в нашем примере 8 битов: n = 22 = 00010110 — ответ 01101000 = 104.

190 Reverse BitsРазбор · 1×

Пример: n = 22 = 00010110, width = 8. Каждый раунд берёт младший бит n и кладёт его в самый низ result.

76543210битn= 2200010110result= 000000000
ещё не прочитанный бит n; пустое место resultмладший бит n и куда он встаётместо, которое только что освободил сдвигбит, уже перенесённый в result0, пришедший в n слеваразвёрнутое число

result начинается пустым: 00000000. n = 22 = 00010110

01/34
сначала · назад · пуск · шаг
Скорость
1function reverseBits(n, width):
2 result = 0
3 repeat width times: // 32 on LeetCode
4 result = result << 1
5 result = result | (n & 1)
6 n = n >> 1
7 return result
состояние
n
22 = 00010110
width
8
result
0 = 00000000
историянажмите шаг, чтобы вернуться

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

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

  1. Биты уходят из n с младшего конца и входят в result тоже снизу, а всё, что уже лежит в result, каждый раунд поднимается на место выше. Поэтому первый взятый из n бит оказывается в result старшим: порядок разворачивается.
  2. Цикл идёт ровно width раз, а не пока n не станет 0. Нули в старших разрядах n становятся нулями в младших разрядах result: здесь, если остановиться на n = 0, вышло бы 13 вместо 104.
  3. Нужны только сдвиги, & и |, поэтому так же работает для любой ширины; на LeetCode она 32.

Сложность

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

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

Решить на LeetCode ↗

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