190. Reverse Bits

NeetCode: Reverse Bits · LeetCode: 190. Reverse Bits · Difficulty: Easy

Reverse the bits of a 32-bit unsigned integer: the lowest bit becomes the highest, and so on. Java has no unsigned int, so the method takes and returns an int that holds the same 32 bits. A value above 2^31 - 1 is a negative int. The examples print results with Integer.toUnsignedString to show the unsigned value, and the cast (int) 4294967293L produces the int with those 32 bits.

Example

Input:  n = 43261596         Output: 964176192
        (00000010100101000001111010011100 -> 00111001011110000010100101000000)
Input:  n = 4294967293       Output: 3221225471

Brute force: go through a bit string

Integer.toBinaryString drops leading zeros and treats the bits as unsigned, so pad the result to 32 characters with zeros, reverse the characters with StringBuilder.reverse, and parse the string back as base 2. The parse uses Long.parseLong because a 32-character string with a leading 1 does not fit in a positive int; the cast (int) keeps the low 32 bits. It allocates strings for what is pure arithmetic.

public class Main {
    static class Solution {
        public int reverseBits(int n) {
            String s = String.format("%32s", Integer.toBinaryString(n)).replace(' ', '0');
            String reversed = new StringBuilder(s).reverse().toString();
            return (int) Long.parseLong(reversed, 2);
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Integer.toUnsignedString(s.reverseBits(43261596)));
        System.out.println(Integer.toUnsignedString(s.reverseBits((int) 4294967293L)));
        System.out.println(Integer.toUnsignedString(s.reverseBits(0)));
    }
}

964176192
3221225471
0

Time: O(32), constant for a fixed width. Space: O(32) for the strings.

Optimal: shift bits across

Repeat 32 times: shift result left to make room, copy in the lowest bit of n with n & 1, and shift n right with the unsigned shift >>> to expose its next bit (the plain >> would copy the sign bit). The bits leave n from the bottom and enter result from the bottom while everything shifts up, which reverses their order. It allocates nothing. The standard library provides the same operation as Integer.reverse.

public class Main {
    static class Solution {
        public int reverseBits(int n) {
            int result = 0;
            for (int i = 0; i < 32; i++) {
                result = (result << 1) | (n & 1);
                n >>>= 1;
            }
            return result;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Integer.toUnsignedString(s.reverseBits(43261596)));
        System.out.println(Integer.toUnsignedString(s.reverseBits((int) 4294967293L)));
        System.out.println(Integer.toUnsignedString(s.reverseBits(0)));
    }
}

964176192
3221225471
0

Time: O(32) = O(1). Space: O(1). Both versions do a fixed amount of work; the second avoids the string allocations. Shifting result left by one when it already has its top bit set drops that bit, which never happens here because result has fewer than 32 bits before each of the 32 shifts.