Reverse Bits

🎯

Reverse Bits

easyBIT_MANIPULATIONAppleAmazonGoogle

Imagine you are working on a low-level networking protocol where you need to reverse the bits of a 32-bit integer to interpret data correctly from a different endian system.

💡 This problem is about manipulating bits directly, which can be confusing at first because it requires thinking about binary representations and bitwise operations rather than normal arithmetic. Beginners often struggle with how to isolate and move bits efficiently.

📋

Problem Statement

Given a 32-bit unsigned integer, reverse its bits and return the resulting integer. Input: A single 32-bit unsigned integer n. Output: The 32-bit unsigned integer that results from reversing the bits of n.

The input is guaranteed to be a 32-bit unsigned integer.You must treat the input as a 32-bit number regardless of language integer size.

💡

Example

Input"n = 43261596"

Output964176192

Binary of input: 00000010100101000001111010011100 Reversed bits: 00111001011110000010100101000000 Decimal output: 964176192

• n = 0 → output = 0 (all bits zero)
• n = 1 → output = 2147483648 (only least significant bit set)
• n = 4294967295 → output = 4294967295 (all bits set)
• n = 2147483648 → output = 1 (only most significant bit set)

⚠️

Common Mistakes

Using signed right shift instead of unsigned right shift

Incorrect bits shifted in for negative numbers, causing wrong output

✅ Use unsigned right shift operators (>>> in Java/JS, logical shift in other languages)

Not masking bits properly when extracting bytes

Higher bits leak into extracted byte, corrupting cache lookup

✅ Use bitwise AND with 0xff to isolate exactly 8 bits

Forgetting to mask final result to 32 bits after shifts

Result may overflow 32 bits in languages with larger integer sizes

✅ Apply mask (e.g., & 0xffffffff) or cast to 32-bit unsigned integer

Looping fewer or more than 32 times in brute force

Partial reversal or incorrect output due to missing bits

✅ Always loop exactly 32 times for 32-bit integers

Using left shift on signed integers without care

May cause sign bit to flip and produce negative numbers

✅ Use unsigned integers or handle sign carefully

🧠

Brute Force (Bit-by-Bit Reversal Using Loop)

💡 This approach exists because it directly follows the problem statement: reversing bits one by one. It helps beginners understand bit extraction and placement before learning optimizations.

Intuition

Extract each bit from the input starting from the least significant bit and build the reversed number by shifting and adding bits from left to right.

Algorithm

1. Initialize result to 0.
2. Iterate 32 times (for each bit in the integer).
3. Extract the least significant bit of n using bitwise AND with 1.
4. Shift result left by 1 to make room for the new bit.
5. Add the extracted bit to result.
6. Shift n right by 1 to process the next bit.
7. After the loop, result contains the reversed bits.

💡 The challenge is to carefully extract and insert bits in the correct order, ensuring no bits are lost or overwritten.

</>

Code

def reverseBits(n: int) -> int:
    result = 0
    for _ in range(32):
        bit = n & 1
        result = (result << 1) | bit
        n >>= 1
    return result

# Driver code
if __name__ == '__main__':
    test_val = 43261596
    print(reverseBits(test_val))  # Expected: 964176192

Line Notes

result = 0Initialize the variable to store reversed bits

for _ in range(32)Process exactly 32 bits of the input integer

bit = n & 1Extract the least significant bit of n

result = (result << 1) | bitShift result left and add the extracted bit

n >>= 1Shift n right to process the next bit

return resultReturn the final reversed bit integer

public class Solution {
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int bit = n & 1;
            result = (result << 1) | bit;
            n >>>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int testVal = 43261596;
        System.out.println(sol.reverseBits(testVal)); // Expected: 964176192
    }
}

Line Notes

int result = 0;Initialize result to accumulate reversed bits

for (int i = 0; i < 32; i++)Loop over all 32 bits

int bit = n & 1;Extract least significant bit of n

result = (result << 1) | bit;Shift result and add extracted bit

n >>>= 1;Unsigned right shift n to process next bit

return result;Return the reversed bits integer

#include <iostream>
using namespace std;

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        for (int i = 0; i < 32; i++) {
            uint32_t bit = n & 1;
            result = (result << 1) | bit;
            n >>= 1;
        }
        return result;
    }
};

int main() {
    Solution sol;
    uint32_t testVal = 43261596;
    cout << sol.reverseBits(testVal) << endl; // Expected: 964176192
    return 0;
}

Line Notes

uint32_t result = 0;Initialize result to store reversed bits

for (int i = 0; i < 32; i++)Iterate over all 32 bits

uint32_t bit = n & 1;Extract least significant bit

result = (result << 1) | bit;Shift result and add extracted bit

n >>= 1;Shift n right to process next bit

return result;Return the reversed bits

var reverseBits = function(n) {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        let bit = n & 1;
        result = (result << 1) | bit;
        n = n >>> 1;
    }
    return result >>> 0;
};

// Test
console.log(reverseBits(43261596)); // Expected: 964176192

Line Notes

let result = 0;Initialize variable to accumulate reversed bits

for (let i = 0; i < 32; i++)Loop through all 32 bits

let bit = n & 1;Extract least significant bit

result = (result << 1) | bit;Shift result left and add bit

n = n >>> 1;Unsigned right shift n to process next bit

return result >>> 0;Return unsigned 32-bit integer result

⏱

Complexity

TimeO(32)

SpaceO(1)

We iterate exactly 32 times, once per bit, so time is constant relative to input size. Space is constant as we only store a few variables.

💡 Since 32 is fixed, this means about 32 operations per input, which is very fast and predictable.

Interview Verdict: Accepted

This approach is simple and always accepted because it directly implements the problem requirements without shortcuts.

🧠

Using Byte-wise Cache Lookup

💡 This approach speeds up reversal by precomputing reversed bits for all 8-bit numbers and then combining results, teaching how caching can optimize bit operations.

Intuition

Since reversing 32 bits is reversing 4 bytes, we can reverse each byte using a precomputed cache and then combine them in reverse order.

Algorithm

1. Precompute a cache array of size 256 where cache[i] is the reversed bits of byte i.
2. Split the 32-bit input into 4 bytes.
3. For each byte, get the reversed byte from the cache.
4. Combine the reversed bytes in reverse order to form the final reversed 32-bit integer.

💡 The key is to realize reversing 32 bits can be done by reversing 4 smaller chunks and reassembling.

</>

Code

class Solution:
    def __init__(self):
        self.cache = [0] * 256
        for i in range(256):
            self.cache[i] = self.reverseByte(i)

    def reverseByte(self, b):
        result = 0
        for _ in range(8):
            result = (result << 1) | (b & 1)
            b >>= 1
        return result

    def reverseBits(self, n: int) -> int:
        result = 0
        for i in range(4):
            byte = (n >> (i * 8)) & 0xff
            result |= self.cache[byte] << ((3 - i) * 8)
        return result

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.reverseBits(43261596))  # Expected: 964176192

Line Notes

self.cache = [0] * 256Initialize cache for all 8-bit values

for i in range(256)Fill cache with reversed bytes

def reverseByte(self, b)Helper to reverse bits in a byte

for _ in range(8)Process each bit in the byte

byte = (n >> (i * 8)) & 0xffExtract the i-th byte from n

result |= self.cache[byte] << ((3 - i) * 8)Place reversed byte in correct position

public class Solution {
    private int[] cache = new int[256];

    public Solution() {
        for (int i = 0; i < 256; i++) {
            cache[i] = reverseByte(i);
        }
    }

    private int reverseByte(int b) {
        int result = 0;
        for (int i = 0; i < 8; i++) {
            result = (result << 1) | (b & 1);
            b >>= 1;
        }
        return result;
    }

    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 4; i++) {
            int byteVal = (n >>> (i * 8)) & 0xff;
            result |= cache[byteVal] << ((3 - i) * 8);
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.reverseBits(43261596)); // Expected: 964176192
    }
}

Line Notes

private int[] cache = new int[256];Cache for reversed bytes

for (int i = 0; i < 256; i++)Precompute reversed bytes

private int reverseByte(int b)Helper to reverse bits in a byte

int byteVal = (n >>> (i * 8)) & 0xff;Extract i-th byte from n

result |= cache[byteVal] << ((3 - i) * 8);Combine reversed bytes in reverse order

return result;Return final reversed integer

#include <iostream>
#include <vector>
using namespace std;

class Solution {
    vector<uint32_t> cache;
public:
    Solution() {
        cache.resize(256);
        for (int i = 0; i < 256; i++) {
            cache[i] = reverseByte(i);
        }
    }

    uint32_t reverseByte(uint32_t b) {
        uint32_t result = 0;
        for (int i = 0; i < 8; i++) {
            result = (result << 1) | (b & 1);
            b >>= 1;
        }
        return result;
    }

    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        for (int i = 0; i < 4; i++) {
            uint32_t byteVal = (n >> (i * 8)) & 0xff;
            result |= cache[byteVal] << ((3 - i) * 8);
        }
        return result;
    }
};

int main() {
    Solution sol;
    cout << sol.reverseBits(43261596) << endl; // Expected: 964176192
    return 0;
}

Line Notes

cache.resize(256);Allocate cache for all 8-bit values

for (int i = 0; i < 256; i++)Precompute reversed bytes

uint32_t reverseByte(uint32_t b)Helper to reverse bits in a byte

uint32_t byteVal = (n >> (i * 8)) & 0xff;Extract i-th byte from n

result |= cache[byteVal] << ((3 - i) * 8);Combine reversed bytes in reverse order

return result;Return final reversed integer

var Solution = function() {
    this.cache = new Array(256);
    for (let i = 0; i < 256; i++) {
        this.cache[i] = this.reverseByte(i);
    }
};

Solution.prototype.reverseByte = function(b) {
    let result = 0;
    for (let i = 0; i < 8; i++) {
        result = (result << 1) | (b & 1);
        b >>= 1;
    }
    return result;
};

Solution.prototype.reverseBits = function(n) {
    let result = 0;
    for (let i = 0; i < 4; i++) {
        let byteVal = (n >>> (i * 8)) & 0xff;
        result |= this.cache[byteVal] << ((3 - i) * 8);
    }
    return result >>> 0;
};

// Test
const sol = new Solution();
console.log(sol.reverseBits(43261596)); // Expected: 964176192

Line Notes

this.cache = new Array(256);Initialize cache array for bytes

for (let i = 0; i < 256; i++)Precompute reversed bytes

reverseByte = function(b)Helper to reverse bits in a byte

let byteVal = (n >>> (i * 8)) & 0xff;Extract i-th byte from n

result |= this.cache[byteVal] << ((3 - i) * 8);Combine reversed bytes in reverse order

return result >>> 0;Return unsigned 32-bit integer

⏱

Complexity

TimeO(1)

SpaceO(256)

Precomputing the cache takes O(256*8) = O(1) time and space. Each query reverses bits in 4 steps using cache lookups, so constant time.

💡 This approach trades a small fixed memory for faster queries, which is useful when reversing bits many times.

Interview Verdict: Accepted

This approach is optimal for repeated calls and shows how caching can speed up bit manipulation.

🧠

Bit Manipulation with Divide and Conquer Masks

💡 This approach uses clever bit masks and shifts to reverse bits in a logarithmic number of steps, teaching how to use bitwise operations to manipulate multiple bits simultaneously.

Intuition

Swap bits in pairs, then in nibbles, then bytes, then 16-bit halves, progressively reversing the bits in fewer operations.

Algorithm

1. Swap odd and even bits using mask 0x55555555.
2. Swap pairs of bits using mask 0x33333333.
3. Swap nibbles (4 bits) using mask 0x0f0f0f0f.
4. Swap bytes using mask 0x00ff00ff.
5. Swap 16-bit halves using mask 0x0000ffff.
6. Return the final reversed integer.

💡 Each step swaps progressively larger groups of bits, effectively reversing the entire 32-bit integer in 5 operations.

</>

Code

def reverseBits(n: int) -> int:
    n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1)
    n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2)
    n = ((n >> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4)
    n = ((n >> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8)
    n = ((n >> 16) | (n << 16)) & 0xffffffff
    return n

# Driver code
if __name__ == '__main__':
    print(reverseBits(43261596))  # Expected: 964176192

Line Notes

n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1)Swap adjacent bits using mask 0x55555555

n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2)Swap pairs of bits using mask 0x33333333

n = ((n >> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4)Swap nibbles using mask 0x0f0f0f0f

n = ((n >> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8)Swap bytes using mask 0x00ff00ff

n = ((n >> 16) | (n << 16)) & 0xffffffffSwap 16-bit halves and mask to 32 bits

return nReturn the reversed bits

public class Solution {
    public int reverseBits(int n) {
        n = ((n >>> 1) & 0x55555555) | ((n & 0x55555555) << 1);
        n = ((n >>> 2) & 0x33333333) | ((n & 0x33333333) << 2);
        n = ((n >>> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4);
        n = ((n >>> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8);
        n = (n >>> 16) | (n << 16);
        return n;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.reverseBits(43261596)); // Expected: 964176192
    }
}

Line Notes

n = ((n >>> 1) & 0x55555555) | ((n & 0x55555555) << 1);Swap adjacent bits using mask 0x55555555

n = ((n >>> 2) & 0x33333333) | ((n & 0x33333333) << 2);Swap pairs of bits using mask 0x33333333

n = ((n >>> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4);Swap nibbles using mask 0x0f0f0f0f

n = ((n >>> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8);Swap bytes using mask 0x00ff00ff

n = (n >>> 16) | (n << 16);Swap 16-bit halves

return n;Return reversed bits

#include <iostream>
using namespace std;

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1);
        n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);
        n = ((n >> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4);
        n = ((n >> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8);
        n = ((n >> 16) | (n << 16)) & 0xffffffff;
        return n;
    }
};

int main() {
    Solution sol;
    cout << sol.reverseBits(43261596) << endl; // Expected: 964176192
    return 0;
}

Line Notes

n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1);Swap adjacent bits using mask 0x55555555

n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);Swap pairs of bits using mask 0x33333333

n = ((n >> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4);Swap nibbles using mask 0x0f0f0f0f

n = ((n >> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8);Swap bytes using mask 0x00ff00ff

n = ((n >> 16) | (n << 16)) & 0xffffffff;Swap 16-bit halves and mask to 32 bits

return n;Return reversed bits

var reverseBits = function(n) {
    n = ((n >>> 1) & 0x55555555) | ((n & 0x55555555) << 1);
    n = ((n >>> 2) & 0x33333333) | ((n & 0x33333333) << 2);
    n = ((n >>> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4);
    n = ((n >>> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8);
    n = (n >>> 16) | (n << 16);
    return n >>> 0;
};

// Test
console.log(reverseBits(43261596)); // Expected: 964176192

Line Notes

n = ((n >>> 1) & 0x55555555) | ((n & 0x55555555) << 1);Swap adjacent bits using mask 0x55555555

n = ((n >>> 2) & 0x33333333) | ((n & 0x33333333) << 2);Swap pairs of bits using mask 0x33333333

n = ((n >>> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4);Swap nibbles using mask 0x0f0f0f0f

n = ((n >>> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8);Swap bytes using mask 0x00ff00ff

n = (n >>> 16) | (n << 16);Swap 16-bit halves

return n >>> 0;Return unsigned 32-bit integer

⏱

Complexity

TimeO(1)

SpaceO(1)

Uses a fixed number of bitwise operations and masks, independent of input size.

💡 This is the fastest approach with minimal memory, ideal for performance-critical code.

Interview Verdict: Accepted

This is the optimal solution often expected in interviews for bit reversal problems.

📊

All Approaches - One-Glance Tradeoffs

💡 For most interviews, coding the brute force or the bit mask approach is best. The cache approach is useful if multiple queries are expected.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(32)	O(1)	No	N/A	Good to explain and code if time-constrained
2. Byte-wise Cache Lookup	O(1)	O(256)	No	N/A	Mention for optimization, code if multiple queries
3. Bit Manipulation with Masks	O(1)	O(1)	No	N/A	Optimal solution to code if comfortable with bitwise ops

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding. Next, discuss optimizations and finally code the best approach you are comfortable with.

How to Present

Step 1: Clarify input size and bit width (32 bits).Step 2: Describe the brute force bit-by-bit reversal approach.Step 3: Mention caching bytes for repeated calls if applicable.Step 4: Present the optimal bit mask and shift method.Step 5: Write clean code and test edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of bitwise operations, ability to optimize, and code correctness on edge cases.

Common Follow-ups

• How would you optimize if you had to reverse bits many times? → Use byte cache lookup.
• Can you reverse bits for 64-bit integers? → Extend masks and loops accordingly.

💡 These follow-ups test your ability to generalize and optimize beyond the basic problem.

🔍

Pattern Recognition

When to Use

1) Problem involves reversing or manipulating bits. 2) Input size fixed (e.g., 32 bits). 3) Requires efficient bitwise operations. 4) Output is integer with bits reversed or rearranged.

Signature Phrases

reverse bits32-bit unsigned integerbitwise AND/OR/shift

NOT This Pattern When

Problems involving arithmetic only or string reversal are different patterns.

Similar Problems

Number of 1 Bits - counting set bits using bit manipulationPower of Two - checking bit patternsHamming Distance - comparing bits between numbers

Practice

1. Given the following code and input, what is the final returned list?

easy

A. [2, 5]

B. [5, 4]

C. [4, 5]

D. [2, 4]

Solution

1. Step 1: Compute xor of all elements

   xor = 2 ^ 4 ^ 2 ^ 5 = (2 ^ 2) ^ 4 ^ 5 = 0 ^ 4 ^ 5 = 1 (binary 0001)

2. Step 2: Find rightmost set bit and partition

   set_bit = xor & (-xor) = 1 & (-1) = 1. Partition nums by bit 1: group1 (bit set): 5, group2 (bit not set): 2,4,2. XOR group1 = 5, XOR group2 = 4.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches unique elements [OK]

Hint: Rightmost set bit partitions unique numbers correctly [OK]

Common Mistakes:

• Mixing order of output
• Incorrect xor calculation
• Miscomputing set bit

2. Identify the bug in the following code snippet for bitwise AND of numbers range:

medium

A. The bit-clearing operation 'right = right & (right - 1)' is incorrect.

B. There is no bug; the code works correctly.

C. The function should return 'left' instead of 'right'.

D. The loop condition should be 'right > left' instead of 'right != left'.

Solution

1. Step 1: Analyze loop condition

   The loop runs while right != left, which fails if right < left, causing infinite loop or incorrect behavior.

2. Step 2: Correct condition

   Changing condition to 'right > left' ensures loop terminates when right reaches or goes below left.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Loop condition must prevent infinite loops and handle equality correctly [OK]

Hint: Loop condition must be 'right > left' to terminate properly [OK]

Common Mistakes:

• Using '!=' instead of '>' causes infinite loops
• Misunderstanding bit-clearing operation
• Returning wrong variable

3. What is the time complexity of the XOR approach to find the missing number in an array of length n containing numbers from 0 to n with one missing?

medium

A. O(n log n) due to sorting inside XOR operations

B. O(1) since XOR is a constant time operation

C. O(n^2) because XOR operations are nested

D. O(n) because it iterates over the range and array once each

Solution

1. Step 1: Identify loops in the XOR approach

   There are two separate loops: one over range 0 to n, and one over the array of length n.

2. Step 2: Calculate total time complexity

   Each loop runs O(n) times, so total time is O(n) + O(n) = O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   No nested loops or sorting, linear time confirmed [OK]

Hint: Two separate linear loops sum to O(n) time [OK]

Common Mistakes:

• Confusing XOR operations as nested loops
• Assuming sorting inside XOR
• Ignoring linear iteration over range

4. What is the time complexity of the brute force iterative division approach to check if a number n is a power of four?

medium

A. O(1) because division is constant time

B. O(n) because it checks every number up to n

C. O(log log n) because division by 4 reduces n faster than by 2

D. O(log n) because the number is divided by 4 each iteration

Solution

1. Step 1: Analyze the loop iterations

   Each iteration divides n by 4, so the number of iterations is proportional to log base 4 of n.

2. Step 2: Express complexity in Big-O notation

   Since log base 4 of n is O(log n), the time complexity is O(log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Loop runs ~log4(n) times, which is O(log n) [OK]

Hint: Dividing by 4 reduces n logarithmically -> O(log n)

Common Mistakes:

• Confusing division steps as O(1)
• Mistaking log log n complexity

5. Consider the following buggy implementation of sum of two integers without + operator. Which line contains the subtle bug that causes incorrect results or infinite recursion?

medium

A. Line 3: base case condition if b == 0

B. Line 6: sum_ calculation using XOR and MASK

C. Line 8: recursive call with sum_ and carry

D. Line 7: carry calculation missing left shift

Solution

1. Step 1: Analyze carry calculation

   Carry must be (a & b) << 1 to shift carry bits to correct position.

2. Step 2: Identify missing left shift causes infinite recursion

   Without shifting, carry never reduces to zero, causing infinite recursion or wrong sum.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Carry missing shift breaks carry propagation [OK]

Hint: Carry must be shifted left by 1 bit [OK]

Common Mistakes:

• Forgetting carry shift
• Incorrect base case
• Not masking intermediate results