☕ DSA Java Articles

Topics › Bit Manipulation › Interview Problems

Reverse Bits

Easy TUF ID 2406 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Reverse the bits of a 32-bit unsigned integer: bit 0 of the input becomes bit 31 of the output, bit 1 becomes bit 30, and so on. Leading zeros count, because the input is always exactly 32 bits wide.

Java has no unsigned int, so the input and output are int values whose bit patterns are the unsigned numbers. An input or output of 2^31 or more shows up as a negative int; for example the unsigned value 3221225471 is the int -1073741825.

Follow-up from LeetCode: if the function is called many times, how would you optimise it?

Example 1

n      = 00000010100101000001111010011100   (43261596)
answer = 00111001011110000010100101000000   (964176192)

Example 2

n      = 11111111111111111111111111111101   (4294967293, the int -3)
answer = 10111111111111111111111111111111   (3221225471, the int -1073741825)

Approach 1: Brute force, go through a string

Intuition. Reversing is easy for strings, so convert the number to its 32-character binary text, reverse the text, and parse it back. Two details decide whether this works. Integer.toBinaryString drops leading zeros (it gives 26 characters for 43261596), so we must left-pad to 32 characters first, or the reversed string loses its trailing zeros. And the reversed value can be 2^31 or more, which Integer.parseInt rejects, so we parse with Integer.parseUnsignedInt.

Algorithm.

  1. Convert n to binary and left-pad with '0' to 32 characters.
  2. Reverse the string.
  3. Parse it as an unsigned base-2 number.
static int bruteForce(int n) {
    String bits = String.format("%32s", Integer.toBinaryString(n)).replace(' ', '0');
    String reversed = new StringBuilder(bits).reverse().toString();
    return Integer.parseUnsignedInt(reversed, 2);
}

Complexity. Time O(32), Space O(32) for the strings. Constant, but it allocates several objects per call and hides the bit logic the interviewer wants to see.

Approach 2: Bit by bit

Intuition. Reversing a decimal number works digit by digit: rev = rev * 10 + n % 10; n /= 10. The binary version replaces “times 10” with a left shift and “mod 10” with n & 1. Each round pops the lowest bit off n and pushes it onto the right end of result; the bit popped first gets pushed left 31 more times and ends up at position 31.

The loop must run exactly 32 times, not “until n is 0”. The leading zeros of n become trailing zeros of the answer, and stopping early leaves them out: n = 1 must give 1 << 31, not 1.

Algorithm.

  1. result = 0.
  2. Repeat 32 times: result = (result << 1) | (n & 1), then n >>>= 1.
  3. Return result.
static int bitByBit(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);   // push n's lowest bit onto the right end of result
        n >>>= 1;                           // unsigned shift, so the sign bit is never copied in
    }
    return result;
}

Dry run, shrunk to 4 bits, on n = 1101 (the answer should be 1011):

round n before n & 1 result after
1 1101 1 0001
2 0110 0 0010
3 0011 1 0101
4 0001 1 1011

Complexity. Time O(32), Space O(1). This is the answer most interviewers expect.

Approach 3: Divide and conquer with masks

Intuition. To reverse a 32-bit word, swap its two 16-bit halves and then reverse each half. To reverse a 16-bit half, swap its two bytes and reverse each byte, and so on down to single bits. Masks let us perform each level of this recursion on all blocks at once:

Why five swaps give the full reversal: write a bit’s position p as five binary digits. Its target 31 - p is p with all five digits flipped. The 16-swap flips the top digit of every position, the 8-swap flips the next one, and so on, so after all five steps every bit sits at 31 - p. The order of the steps does not even matter. This is the algorithm inside Integer.reverse.

static int divideAndConquer(int n) {
    n = (n >>> 16) | (n << 16);                                // swap the two 16-bit halves
    n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);    // swap the bytes inside each half
    n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);    // swap the nibbles inside each byte
    n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);    // swap the bit pairs inside each nibble
    n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);    // swap the bits inside each pair
    return n;
}

Complexity. Time O(1): five steps of a few operations each, with no loop. Space O(1). All shifts are >>>, so bits moving down never drag copies of the sign bit along.

Approach 4: Lookup table, for the “called many times” follow-up

Intuition. If the function runs millions of times, precompute something once. A table of all 65,536 reversed 16-bit values is possible, but 256 reversed bytes are enough: reverse each of the four bytes with one lookup and place it in the mirrored byte slot (byte 0 goes to byte 3, byte 1 to byte 2, and so on). The table is filled once using Approach 2; reversing an 8-bit value in a 32-bit word puts its bits in the top byte, hence the >>> 24.

static final int[] REVERSED_BYTE = buildByteTable();

static int[] buildByteTable() {
    int[] table = new int[256];
    for (int b = 0; b < 256; b++) table[b] = bitByBit(b) >>> 24;   // the 8 bits of b land in the top byte
    return table;
}

static int byteTable(int n) {
    return (REVERSED_BYTE[n & 0xff] << 24)
            | (REVERSED_BYTE[(n >>> 8) & 0xff] << 16)
            | (REVERSED_BYTE[(n >>> 16) & 0xff] << 8)
            | REVERSED_BYTE[n >>> 24];
}

Complexity. O(256) one-time setup and 1 KB of memory, then four lookups, shifts and ORs per call. Approach 3 is equally fast with no table, so in practice either is a good answer; just call Integer.reverse in production code.

Edge cases and pitfalls