💬 Discord
Sign In
NeetCode #857LC-190EasyBit ManipulationBlind 75NC 150NC 250
← Back to All Problems

#857 · #190 · Reverse Bits(颠倒二进制位)

📌 Problem Statement & Constraints

Reverse the bits of a given 32-bit unsigned integer n and return the result. The input is treated as a fixed 32-bit value, so leading zeros are significant: reversing 1 must yield 2^31.

💡 Core Algorithmic Approaches

  1. The straightforward loop runs exactly 32 times: shift the result left to make room, OR in the lowest bit of n, then shift n right.
  2. The fixed iteration count is essential -- a while n: loop would stop early and drop the leading zeros.
  3. A second approach swaps bit blocks in a divide-and-conquer manner: 16-bit halves, then 8, 4, 2 and 1, using masks.
  4. The mask method uses only five steps and is the classic bit-twiddling answer.

💻 Benchmark Python3 Implementation

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for _ in range(32):
            res = (res << 1) | (n & 1)   # append the lowest bit of n
            n >>= 1
        return res


# Divide and conquer: swap 16-, 8-, 4-, 2- and 1-bit halves
class Solution2:
    def reverseBits(self, n: int) -> int:
        n = ((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16)
        n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)
        n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)
        n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)
        n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)
        return n

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(32) = O(1) for the loop; O(1) for the five mask steps.
💾 Space Complexity
O(1): one accumulator.

⚠️ Interview Pitfalls & Follow-ups

  • Looping while n is non-zero: leading zeros are skipped, so the result lands in the wrong positions.
  • Reversing only the significant bits: the problem fixes the width at 32, so always iterate 32 times.
  • Forgetting the OR: writing res = res << 1 without OR-ing the current bit loses it entirely.
  • Using a byte-reversal table: valid but over-engineered for a fixed 32-bit width.