easy Reverse Bits

Reverse Bits

Problem. You are given a 32-bit unsigned integer. Return the value whose binary representation is the input's 32 bits read in reverse order — bit 0 becomes bit 31, bit 1 becomes bit 30, and so on. The classic example: the input 00000010100101000001111010011100 (decimal 43261596) reverses to 00111001011110000010100101000000 (decimal 964176192).

This looks trivial — "just flip the bits around" — and it is, once. The reason it shows up in real systems (FFT butterfly indexing, hashing, Gray-code hardware) is that it is often called in a tight loop, so the difference between an O(w) per-bit method and an O(1) constant-step method actually matters. We build both and then decide when each earns its place.

Why "unsigned" is the whole trap

The problem is stated over an unsigned 32-bit word, but Java has no unsigned int — its int is a signed two's-complement 32-bit value. That single fact spawns every bug on this page. When the top (sign) bit is set and you shift right with Java's arithmetic >>, the sign bit is copied into the vacated high positions (sign extension), so you do not get the "empty" bit you were expecting — you get a 1. You must use Java's logical right shift >>>, which always feeds in 0. Go sidesteps the whole issue: declare the value as uint32 and >> is already logical.

Approach 1 — build the answer one bit at a time

The mechanical, always-correct method. Walk the input 32 times. Each pass, peel off the input's lowest bit with n & 1 and push it into the lowest slot of the result; then shift the result up by one to make room for the next bit, and shift the input down by one to expose its next bit. Because the result is shifted left on every step, the bit you pushed first ends up highest — which is exactly the reversal.

The order inside the loop matters: do result = (result << 1) | (n & 1) first (this both makes room and deposits the new bit in one expression), then advance n.

Traced example (8-bit illustration of the same loop)

Reversing 32 bits in a table is unreadable, so watch the identical loop reverse an 8-bit value — the mechanism is bit-for-bit the same, just wider. Input n = 00000011 (decimal 3); its 8-bit reversal is 11000000 (decimal 192).

Final result = 11000000 = 192 — the input's bits in reverse. The two 1s that were in the lowest positions were pushed in first and rode all the way up to the top. Over a real 32-bit word the loop runs 32 times instead of 8; the logic is unchanged.

Java: bit-by-bit

public class Solution {
    // treat n purely as 32 unsigned bits
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1); // make room, drop in n's low bit
            n >>>= 1;                          // LOGICAL shift: feeds 0, never the sign bit
        }
        return result;
    }

    public static void main(String[] args) {
        int r = new Solution().reverseBits(43261596);
        // print as unsigned to see the true 32-bit value
        System.out.println(r & 0xffffffffL); // 964176192
    }
}

Go: bit-by-bit

package main

import "fmt"

// uint32 makes "unsigned" explicit; >> is already logical here.
func reverseBits(n uint32) uint32 {
    var result uint32 = 0
    for i := 0; i < 32; i++ {
        result = (result << 1) | (n & 1)
        n >>= 1
    }
    return result
}

func main() {
    fmt.Println(reverseBits(43261596)) // 964176192
}

Approach 2 — divide & conquer, constant number of steps

Reversing is separable: reversing the whole word equals swapping its two 16-bit halves, then recursively reversing inside each half. Reversing inside a 16-bit half equals swapping its two 8-bit quarters, then reversing inside those — and so on down to swapping adjacent single bits. Because each level is done with two masked shifts over the entire word in parallel, the whole reversal is just five steps regardless of word size (log₂32 = 5):

1. swap 16-bit halves
2. swap 8-bit groups within each half
3. swap 4-bit groups
4. swap 2-bit groups
5. swap adjacent single bits

Each step uses a pair of masks that select the "left" and "right" members of every group at that scale. For the adjacent-bit swap, 0xaaaaaaaa is every odd-position bit (1010…) and 0x55555555 is every even-position bit (0101…): shift the odd bits down one, shift the even bits up one, OR them together. The 2-bit masks are 0xcccccccc/0x33333333, the nibble masks 0xf0f0f0f0/0x0f0f0f0f, and so on. No loop, no data-dependent branches — five fixed instructions.

Why it equals the loop: after all five swaps, the bit originally at position i has had each of its 5 address bits flipped (16-swap flips bit 4 of the address, 8-swap flips bit 3, …, 1-swap flips bit 0), so it lands at address 31 - i — the definition of reversal. We verified both methods return the identical 964176192 for the sample input in both languages.

Java: divide & conquer (O(1) steps)

public int reverseBits(int n) {
    n = (n >>> 16) | (n << 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;
}
// NOTE: masks like 0xff00ff00 are negative int literals, but the
// bit patterns are correct; >>> (not >>) is essential so the
// high group is not sign-extended. Or just call Integer.reverse(n).

Go: divide & conquer (O(1) steps)

func reverseBits(n uint32) uint32 {
    n = (n >> 16) | (n << 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
}
// stdlib: math/bits.Reverse32(n) does exactly this.

Complexity

• Bit-by-bit: the loop runs the word width w = 32 times, each iteration O(1) → O(w) = O(32) = O(1) per call in a fixed word size, but with a constant factor of 32.
• Divide & conquer: exactly log₂w = 5 masked shift-pairs, no loop → O(log w) instructions, a strictly smaller constant. Both are O(1) space.

For a single call the difference is noise. In a hot loop reversing millions of indices, the D&C form (or the intrinsic that compiles to it) is measurably faster because it has no per-bit branch.

Judgment layer — which to reach for, and when NOT to

• In an interview, write the bit-by-bit loop first. It is obviously correct, easy to explain, and the interviewer can watch you reason about >>> vs >>. Then say "if this is on a hot path I'd switch to the divide-and-conquer version or the intrinsic" — naming the trade-off is the staff signal, not memorizing the masks.
• Reach for divide & conquer only when profiling shows this is hot (FFT bit-reversal permutation, a hash mixer called per element). The masks are error-prone to type from memory; if you just need it to work, call the builtin: Integer.reverse(n) in Java, bits.Reverse32(n) from math/bits in Go. Both are typically one hardware instruction on modern CPUs.
• Do NOT hand-roll either in production if a builtin exists — it is faster and cannot be typed wrong. The hand-rolled versions exist to prove you understand what the builtin does.
• vs. a lookup table (reverse bytes via a 256-entry table, then reassemble): a real alternative for reversing many values on hardware without a reverse instruction — O(1) with 4 table reads and shifts, at the cost of 256 bytes of cache. Mention it if asked to optimize for an embedded target.

Traps & edge cases

• Java >> vs >>>: using arithmetic >> sign-extends when bit 31 is set, corrupting the result. Always >>> here.
• Printing the answer in Java: a reversed value with bit 31 set prints as a negative int. It is not wrong — it is the same 32 bits — but to display the intended unsigned value use n & 0xffffffffL or Integer.toUnsignedString(n). (Our sample 964176192 happens to be positive, so this bites you on other inputs.)
• Go: take and return uint32, not int. Using int (64-bit on most platforms) would reverse over the wrong width.
• Mask literals: the D&C masks are 32-bit patterns; do not accidentally widen them.

Authored for this guide from first principles (LeetCode 190). Both code paths compiled and run in Java 8 and Go 1.25; the traced 8-bit example and the 32-bit sample (43261596 → 964176192) were verified bit-for-bit against execution.