Reverse Bits

Easy#190bit by bit

You get an unsigned integer of a fixed width — 32 bits on LeetCode. Write its bits in the opposite order, the lowest first, and return the number they make; the zeros at the top count too. To draw every bit, our example has 8 bits: n = 22 = 00010110 — the answer is 01101000 = 104.

190 Reverse BitsWalkthrough · 1×

Example: n = 22 = 00010110, width = 8. Each round takes the lowest bit of n and puts it at the bottom of result.

76543210bitn= 2200010110result= 000000000
a bit of n not read yet; an empty place of resultthe lowest bit of n and where it landsthe place the shift just freeda bit already moved into resulta 0 that came into n from the leftthe reversed number

result starts empty: 00000000. n = 22 = 00010110

01/34
restart · back · play · step
Speed
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
state
n
22 = 00010110
width
8
result
0 = 00000000
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Bits leave n from the lowest and enter result at the lowest, while everything already in result moves up one place each round. So the first bit taken from n ends up the highest in result: the order is reversed.
  2. The loop runs exactly width times, not until n is 0. The zeros at the top of n become the zeros at the bottom of result: here, stopping when n hits 0 would give 13 instead of 104.
  3. Only shifts, & and | are used, so it works the same for any width; on LeetCode the width is 32.

Complexity

Time O(w), where w is the width: one round per bit, 32 on LeetCode, so in effect O(1). Memory O(1): two 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.