Reverse Bits

Q: Why do infrastructure roles meet bit reversal?

Bit and byte order matters whenever data crosses a wire or a file format: network byte order versus host byte order, reading fields out of packet headers, or decoding binary log formats. Reversing bits is the simplest exercise in handling fixed-width unsigned values correctly, especially in languages like Java that only have signed integers.

easyBits

You get a 32-bit unsigned integer n. Reverse the order of its 32 bits, so bit 0 becomes bit 31, bit 1 becomes bit 30, and so on, and return the result as an unsigned integer.

Leading zeros count: all 32 positions take part in the reversal. In Java, which has no unsigned int, the input and output are held in an int and should be read as unsigned bit patterns.

Examples

Example 1

Input: n = 1

Output: 2147483648

Explanation: Only bit 0 is set. After reversing, only bit 31 is set, which is 2^31. (In Java the returned int prints as -2147483648; Integer.toUnsignedString shows 2147483648.)

Example 2

Input: n = 6

Output: 1610612736

Explanation: 6 has bits 1 and 2 set. They move to bits 30 and 29: 2^30 + 2^29 = 1610612736.

Hints

Approach

Move bits one at a time with shifts.

result = 0.
Repeat 32 times: shift result left by one to make room, OR in the lowest bit of n (n & 1), then shift n right by one.
Return result.

The first bit taken from n is shifted left 31 more times and ends in position 31, which is exactly the reversal. In Java, use >>> so the sign bit is not copied in as n shifts; the result is the correct bit pattern even when it looks negative as a signed int.

ComplexityTime O(32) = O(1)Space O(1)

Python

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for _ in range(32):
            result = (result << 1) | (n & 1)  # append n's lowest bit
            n >>= 1
        return result

Follow-up questions

The function is called millions of times. How would a 256-entry lookup table of reversed bytes make it faster?
Reverse the byte order of a 32-bit integer instead of the bit order (the host-to-network conversion).

Frequently asked questions

Yes, with divide-and-conquer masks: swap the two 16-bit halves, then swap bytes within each half, then nibbles, pairs and single bits, each with one shift-and-mask step such as ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1). That is five steps instead of 32 and is essentially how Java's Integer.reverse works.

Bit and byte order matters whenever data crosses a wire or a file format: network byte order versus host byte order, reading fields out of packet headers, or decoding binary log formats. Reversing bits is the simplest exercise in handling fixed-width unsigned values correctly, especially in languages like Java that only have signed integers.