Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Reverse Bits

Reverse Bits

Master this topic with zero to advance depth.

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Easy

Examples

Input: n = 43261596
Output: 964176192

43261596 (00000010100101000001111010011100) reversed is 964176192 (00111001011110000010100101000000).

Approach 1

Level I: Brute Force (Iterate and Shift)

Intuition

Iterate through each of the 32 bits of the input. In each step, shift the result left and add the last bit of the input. Then shift the input right.

Thought Process

  1. Initialize res = 0.
  2. Loop 32 times:
    • Check the last bit of n: n & 1.
    • Shift res left and add that bit: (res << 1) + (n & 1).
    • Right shift n by 1.
  3. Return res.

Pattern: Bitwise Result Construction

⏱ O(1) - Always 32 iterations.💾 O(1) - Constant extra space.
java
public class Solution {
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res = (res << 1) | (n & 1);
            n >>= 1;
        }
        return res;
    }
}
Approach 2

Level II: Byte-by-Byte Lookup (Caching)

Intuition

A 32-bit integer consists of 4 bytes. We can precompute or manually reverse the bits for each byte (8 bits) and then combine them. This is faster when multiple calls are made as the byte reversals can be cached.

⏱ $O(1)$ - Proportional to number of bytes (4).💾 $O(1)$ - Small lookup table or fixed reversal logic.
java
public class Solution {
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 4; i++) {
            res = (res << 8) | reverseByte((n >> (i * 8)) & 0xFF);
        }
        // Adjust result because the loop constructs it in reverse order
        return Integer.reverse(n);
    }
    
    private int reverseByte(int b) {
        int r = 0;
        for (int i = 0; i < 8; i++) {
            r = (r << 1) | ((b >> i) & 1);
        }
        return r;
    }
}
Approach 3

Level III: Optimal (Divide and Conquer)

Intuition

We can reverse the bits using a series of mask and shift operations. First, swap adjacent bits, then swap adjacent pairs, then adjacent nibbles (4 bits), and so on.

Thought Process

  1. Swap bits 1-by-1: n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1)
  2. Swap bits 2-by-2: n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2)
  3. Swap bits 4-by-4: n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4)
  4. Swap bits 8-by-8: n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8)
  5. Swap bits 16-by-16: n = (n >>> 16) | (n << 16)

Pattern: Parallel Bit Processing

⏱ O(1) - Constant number of bitwise operations.💾 O(1) - Constant space.
java
public class Solution {
    public int reverseBits(int n) {
        n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1);
        n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4);
        n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8);
        n = (n >>> 16) | (n << 16);
        return n;
    }
}
← Previous QuestionNumber of 1 Bits
Next Question →Sum of Two Integers