Log inSign up
easyLeetCodeNot Started

Reverse Bits

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

Reverse the bits of a given 32-bit unsigned integer.

Note: - In some languages like Java, there is no unsigned integer type. In this case, both input and output will be given as signed integers. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned. - Follow up: If this function is called many times, how would you optimize it?

Example 1 · Example 1: Standard 32-bit Integer:

Input: n = 00000010100101000001111010011100 (43261596)
Output: 00111001011110000010100101000000 (964176192)
Explanation: Reversing the binary sequence flips all 32 bit indices.

Example 2 · Example 2: Trailing Set Bit:

Input: n = 11111111111111111111111111111101
Output: 10111111111111111111111111111111 (3221225471)
Explanation: Bit 1 was 0, after reversing bit 30 becomes 0.

Constraints:

  • Input is a 32-bit unsigned integer

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Implement bitwise mirroring using sequential shift accumulation.
  • Master the divide-and-conquer hierarchical bit swapping technique.
  • Design 8-bit cache lookup tables for ultra-fast repeated queries.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Invert or mirror the binary layout of a fixed-width integer.
  • High-throughput multi-query optimization request.
  • Symmetric bit manipulation.

Algorithmic Decision Tree:

  • Use 32-step shift loop for clean readability.
  • Use parallel SWAR mask swapping for branchless O(1) performance.

Connected Patterns:

Number of 1 BitsCounting BitsHamming Distance

1. String Format and Reverse

Intuition

Build a 32-character string of 0s and 1s representing n. Reverse the string characters. Convert the reversed string back into a 32-bit unsigned integer.

When to apply: Basic prototyping.

Algorithm

  1. Step 1: Pad binary string of n to length 32.
  2. Step 2: Reverse the string.
  3. Step 3: Parse reversed string as unsigned integer.
  4. Step 4: Return integer.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <bitset>
4#include <algorithm>
5
6using namespace std;
7
8uint32_t reverseBitsBrute(uint32_t n) {
9 bitset<32> bs(n);
10 string s = bs.to_string();
11 reverse(s.begin(), s.end());
12 bitset<32> rev(s);
13 return (uint32_t)rev.to_ulong();
14}
15
16int main() {
17 cout << "Brute (43261596): " << reverseBitsBrute(43261596) << endl; // 964176192
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(32) = O(1)
  • Space complexity: O(32) string storage

2. 32-Step Bit Shift Accumulation

Intuition

Initialize res = 0. For 32 iterations, left-shift res by 1 and OR with n & 1. Then right-shift n logically by 1 (n >>>= 1). Return res.

When to apply: Standard canonical implementation in most interviews.

Algorithm

  1. Step 1: Set res = 0.
  2. Step 2: Loop 32 times: res = (res << 1) | (n & 1), n >>>= 1.
  3. Step 3: Return res.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5uint32_t reverseBitsShift(uint32_t n) {
6 uint32_t res = 0;
7 for (int i = 0; i < 32; ++i) {
8 res = (res << 1) | (n & 1);
9 n >>= 1;
10 }
11 return res;
12}
13
14int main() {
15 cout << "Shift (43261596): " << reverseBitsShift(43261596) << endl; // 964176192
16 return 0;
17}

Time & Space Complexity

  • Time complexity: O(32) = O(1)
  • Space complexity: O(1)

3. Divide-and-Conquer Parallel Mask Swapping

Intuition

Hierarchically reverse bits similar to merge sort: swap the two 16-bit halves, then swap 8-bit bytes, 4-bit nibbles, 2-bit pairs, and adjacent single bits using bitwise masks: 0xff00ff00, 0xf0f0f0f0, 0xcccccccc, and 0xaaaaaaaa.

When to apply: Optimal for production and competitive programming: branch-free, 5 cycles.

Algorithm

  1. Step 1: n = (n >> 16) | (n << 16).
  2. Step 2: n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8).
  3. Step 3: n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4).
  4. Step 4: n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2).
  5. Step 5: n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1).
  6. Step 6: Return n.

Bit Shift Accumulation Trace for 4-bit demonstration

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Step 1: n = 1010
Visual state
Values and pointers at this exact step
pointers
S
0
0
↑ bit 0
Check / comparison
res = 0
Decision / next transition
First bit appended.
Why this step matters

Step 1: n = 1010. Lowest bit = 0. res = (0 << 1) | 0 = 0. n becomes 0101.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 uint32_t reverseBits(uint32_t n) {
8 n = (n >> 16) | (n << 16);
9 n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
10 n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
11 n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
12 n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
13 return n;
14 }
15};
16
17int main() {
18 Solution sol;
19 cout << "Optimal (43261596): " << sol.reverseBits(43261596) << endl; // 964176192
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(1) (5 arithmetic operations)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — String ReversalO(32) = O(1)O(32)Convert to 32-character binary string, reverse string characters, parse back to integer.String building and parsing.
2.Better — 32-Step Bit Shift AccumulationO(32) = O(1)O(1)Loop 32 times: res = (res << 1) | (n & 1), n >>>= 1.32 sequential shift steps.
3.Optimal — Divide-and-Conquer Mask SwappingOptimalO(1) (5 parallel instructions)O(1)Hierarchically swap 16-bit, 8-bit, 4-bit, 2-bit, and 1-bit chunks in 5 bitwise steps.Hardware arithmetic.

Common Pitfalls & Crucial Edge Cases

Looping until n == 0 instead of 32 iterations

If n has trailing zeros, a while (n > 0) loop terminates early, placing bits in the wrong positions. You MUST iterate all 32 bits.

Signed right shift in Java/JS

Using >> instead of >>> replicates sign bits for negative inputs.

Missing `>>> 0` in JavaScript

Bitwise operators in JS return signed 32-bit integers, displaying negative numbers for outputs with bit 31 set.

Crucial Edge Cases to Validate:

  • n = 0 — Reversing 32 zeros produces 0.
  • n = 1 (0x00000001) — Lowest bit becomes MSB (bit 31), yielding 0x80000000 (2147483648).
  • Palindromic bit patterns (e.g. 0xFFFFFFFF) — Reversing all 1s produces all 1s.
  • JavaScript signed 32-bit integers — Bitwise operations in JS operate on signed 32-bit ints; append >>> 0 to convert to unsigned 32-bit int.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Present the 32-bit loop first, then blow the interviewer away with the O(1) SWAR divide-and-conquer mask swaps.
  2. Address the follow-up question proactively: mention the 256-element byte lookup table cache strategy.
  3. Highlight the need for unsigned right shifts (>>>) to preserve clean zero-padding.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the basic idea of the 32-step iterative bit reversal?

2.How does the Divide-and-Conquer (SWAR) approach reverse 32 bits in just 5 operations?

3.If this function is called billions of times in a real-time system, how should it be optimized?

Back to DSA Sheet