Reverse Bits

• Convert the integer n to its binary string representation using Integer.toBinaryString(n).
• Pad the resulting string with leading zeros to ensure it has a length of 32.
• Create a StringBuilder with this 32-bit string.
• Reverse the StringBuilder.
• Convert the reversed StringBuilder back to a string.
• Parse the reversed binary string. Since the value might exceed Integer.MAX_VALUE, parse it as a long using Long.parseLong(string, 2) and then cast the result to an int.

The core idea is to leverage built-in string manipulation functions. First, we need to get the 32-bit binary representation of the input integer n. Standard library functions like Integer.toBinaryString(n) do not produce a 32-bit string with leading zeros, so manual padding is required. Once we have the 32-bit string, we can use a StringBuilder to reverse it efficiently. Finally, the reversed binary string needs to be converted back to an integer. Since the reversed string can represent a number larger than Integer.MAX_VALUE (e.g., if the original LSB was 1, the new MSB will be 1, making it a large positive or negative number in signed context), it's safer to parse it as a long and then cast it to an int. This correctly handles the unsigned nature of the problem within Java's signed integer context.

1public class Solution {2    // you need to treat n as an unsigned value3    public int reverseBits(int n) {4        String binaryString = Integer.toBinaryString(n);5        6        // Pad with leading zeros to make it 32 bits long7        while (binaryString.length() < 32) {8            binaryString = "0" + binaryString;9        }10        11        StringBuilder reversedBuilder = new StringBuilder(binaryString);12        reversedBuilder.reverse();13        14        // Use Long.parseLong to handle unsigned values that would overflow a signed int15        // when the most significant bit is 1.16        long resultAsLong = Long.parseLong(reversedBuilder.toString(), 2);17        return (int) resultAsLong;18    }19}

• Initialize an integer variable result to 0.
• Loop 32 times, for each bit in the integer.
• In each iteration:
  1. Left shift result by 1 (result <<= 1;) to make space for the next bit.
  2. Extract the least significant bit (LSB) of n using a bitwise AND with 1 (n & 1).
  3. Add this LSB to result using a bitwise OR (result |= ...).
  4. Right shift n by 1 using the unsigned right shift operator (n >>>= 1;) to discard the LSB and process the next bit.
• After 32 iterations, return result.

We initialize a result variable, say result, to 0. We will build the final reversed number in this variable. We loop 32 times, once for each bit of the integer. In each iteration, we first make space in our result number for the next bit by left-shifting it. Then, we extract the least significant bit (LSB) from the input number n and add it to our result. Finally, we discard the LSB from n by right-shifting it. It is crucial to use the unsigned right shift (>>>) to ensure that when a '1' is shifted from the most significant bit position (in the case of negative numbers), a '0' is shifted in, which correctly models the behavior of an unsigned integer. After 32 iterations, n will be 0, and result will hold all the bits of the original n in reverse order.

1public class Solution {2    // you need to treat n as an unsigned value3    public int reverseBits(int n) {4        int result = 0;5        for (int i = 0; i < 32; i++) {6            // Make space for the next bit7            result <<= 1;8            9            // Get the LSB of n and add it to result10            result |= (n & 1);11            12            // Discard the LSB of n. Use unsigned right shift.13            n >>>= 1;14        }15        return result;16    }17}

• Preprocessing (One-time cost):
  1. Create a cache, an integer array of size 256 (cache[256]).
  2. Iterate from i = 0 to 255. For each i, compute its 8-bit reversal and store it in cache[i].
• reverseBits Function (Per-call):
  1. Break the 32-bit input n into four 8-bit bytes.
  2. Look up the pre-computed reversed value of each byte from the cache.
  3. Assemble the final result by shifting these reversed bytes to their new positions and combining them with bitwise OR.

     • 1result = (reversed_byte0 << 24) | (reversed_byte1 << 16) | (reversed_byte2 << 8) | reversed_byte3

The key insight is that reversing a 32-bit number is equivalent to reversing its four 8-bit bytes and then reversing the order of those bytes. For example, if n = B3 B2 B1 B0 (where B_i are bytes from most to least significant), then reverse(n) = reverse(B0) reverse(B1) reverse(B2) reverse(B3). We can pre-calculate reverse(byte) for all 256 possible byte values and store them. This cache is typically created once using a static initializer block. Then, for each call to reverseBits, we simply perform four byte extractions, four table lookups, three shifts, and three OR operations, which is significantly faster than iterating 32 times.

1public class Solution {2    // A static cache to store the reversed value of each of the 256 possible bytes.3    private static final int[] cache = new int[256];4 5    // The static initializer block runs once when the class is loaded, 6    // pre-populating the cache.7    static {8        for (int i = 0; i < 256; i++) {9            int b = i;10            int reversed = 0;11            for (int j = 0; j < 8; j++) {12                reversed <<= 1;13                reversed |= (b & 1);14                b >>= 1;15            }16            cache[i] = reversed;17        }18    }19 20    public int reverseBits(int n) {21        // Deconstruct n into 4 bytes, look up their reversed values in the cache,22        // and reconstruct the final integer.23        // Note the use of >>> (unsigned right shift) for correctness.24        return (cache[n & 0xFF] << 24) |25               (cache[(n >>> 8) & 0xFF] << 16) |26               (cache[(n >>> 16) & 0xFF] << 8) |27               (cache[(n >>> 24) & 0xFF]);28    }29}