Reverse Bits

Given a non-negative int num, reverse the bits of its binary representation and return the result. Only the significant bits count: leading zeros are ignored.

Example

Input:  13   Output: 11    (1101 -> 1011)
Input:  6    Output: 3     (110  -> 011)
Input:  1    Output: 1

Brute force: go through a string

Format the number in binary, reverse the characters, and parse the result back.

public class Main {
    static int reverseBits(int num) {
        String reversed = new StringBuilder(Integer.toBinaryString(num)).reverse().toString();
        return Integer.parseInt(reversed, 2);
    }

    public static void main(String[] args) {
        for (int n : new int[] {13, 6, 1, 0}) {
            System.out.println(n + " -> " + reverseBits(n));
        }
    }
}

13 -> 11
6 -> 3
1 -> 1
0 -> 0

Time: O(b), where b is the number of bits. Space: O(b) for the string.

Integer.toBinaryString formats the number as unsigned binary text without leading zeros, and Integer.parseInt(text, 2) reads binary text back. For a non-negative int, the reversed value has at most as many significant bits as the input, so it fits in an int.

Optimal: shift bits across

Take the lowest bit of num with num & 1, append it to the result by shifting the result left, then drop that bit from num with num >>= 1. Stop when num becomes 0, so leading zeros are never read.

public class Main {
    static int reverseBits(int num) {
        int result = 0;
        while (num > 0) {
            result = (result << 1) | (num & 1);
            num >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        for (int n : new int[] {13, 6, 1, 0}) {
            System.out.println(n + " -> " + reverseBits(n));
        }
    }
}

13 -> 11
6 -> 3
1 -> 1
0 -> 0

Time: O(b). Space: O(1).

Fixed-width variant (LeetCode 190)

LeetCode 190 reverses all 32 bits, so leading zeros become trailing zeros: 13 becomes 10110000000000000000000000000000. Run the same loop exactly 32 times, or use Integer.reverse, which reverses all 32 bits of an int. The result has the top bit set, so Java reads it as a negative int. Integer.toUnsignedString prints it as the unsigned value LeetCode expects:

public class Main {
    public static void main(String[] args) {
        int reversed = Integer.reverse(13);
        String bits = String.format("%32s", Integer.toBinaryString(reversed)).replace(' ', '0');
        System.out.println(bits);
        System.out.println(Integer.toUnsignedString(reversed));
        System.out.println(reversed);
    }
}

10110000000000000000000000000000
2952790016
-1342177280

Edge cases

• Zero: has no significant bits, so the result is 0.
• Trailing zeros: become leading zeros and disappear: 8 (1000) becomes 1.