Skip to main content
DSA patterns

Reverse Bits

easyBitsCiscoPalo Alto NetworksDell

Problem statement

You are given a number n and should treat it as exactly 32 bits, padding with leading zeros if needed. Reverse the order of those 32 bits — the last bit becomes the first, the second-to-last becomes the second, and so on — and return the number the reversed bits represent.

n is between 0 and 2³¹ − 2 and is always even. Because its lowest bit is 0, the highest bit of the answer is 0 too, so the answer always fits in a normal signed 32-bit integer.

Examples

Example 1

Input: n = 43261596

Output: 964176192

Explanation: In 32 bits, 43261596 is 00000010100101000001111010011100. Read backwards, that is 00111001011110000010100101000000, which is 964176192.

Example 2

Input: n = 2147483644

Output: 1073741822

Explanation: 2147483644 is a 0, then twenty-nine 1s, then two 0s. Reversed, it becomes two 0s, twenty-nine 1s and a 0, which is 1073741822.

Hints

Hint 1: Writing the number as a 32-character string of 0s and 1s, reversing it, and reading it back works. Can you do it without strings?

Approach

Optimal: Bit-by-bit shifting

Intuition

Think of taking cards off the bottom of one stack and putting them on top of another: the order flips. Here, the "bottom card" of n is its lowest bit, which n & 1 reads. Moving it onto result means shifting result left by one (making an empty slot at the bottom) and putting the bit there with |. Then n >> 1 throws away the bit we just used, so the next bit becomes the lowest.

After 32 rounds, the bit that was lowest in n has been shifted up 31 places to the top of result, and the bit that was highest in n sits at the bottom. That is the reversed number. We always do exactly 32 rounds — not "until n is 0" — so the leading zeros of n become trailing zeros of the answer.

Steps

  1. Set result = 0.
  2. Repeat 32 times:
    • Shift result left by 1.
    • Set the lowest bit of result to n & 1 (using |).
    • Shift n right by 1.
  3. Return result.

Dry run

Shown on a 4-bit example so it fits: n = 1011 (reversed should be 1101).

round n & 1 result after n after
1 1 0001 0101
2 1 0011 0010
3 0 0110 0001
4 1 1101 0000

The real code does the same for 32 rounds. Edge case: n = 0 gives 32 zeros → 0. Because the loop count is fixed, a small n like 2 correctly becomes 1073741824, with its 1 bit moved to position 30.

Complexity

Time O(1) - The loop always runs exactly 32 times, and each round does three tiny bit operations: an AND, and two shifts. That is about 100 machine operations per call, with no strings at all. If the width were b bits it would be O(b), but the width is fixed at 32.

Space O(1) - Only two numbers are kept: what is left of `n` and the `result` being built. Nothing else is allocated.

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


if __name__ == "__main__":
    print(Solution().reverseBits(43261596))  # 964176192
    print(Solution().reverseBits(2147483644))  # 1073741822
RecapThe whole problem in a few lines, for the night before
  • Spot it: reverse the 32 bits of an unsigned integer
  • Idea: loop 32 times: shift the result left, add the lowest bit of n, then shift n right
  • Cost: O(1) time (32 steps), O(1) space
  • Trap: always do all 32 steps, even when the leading bits are zero, and use an unsigned shift in Java (>>>)

Interview follow-ups

  • This function is called millions of times. How would you speed it up?

    Precompute a table of the reversed value for all 256 possible bytes. To reverse 32 bits, split n into its 4 bytes, look each one up, and put the reversed bytes back in the opposite order. That is 4 lookups instead of 32 loop rounds. The table costs 256 entries of memory, built once. This is the follow-up LeetCode itself asks.

  • Reverse the bits of a 64-bit number instead.

    Loop 64 times instead of 32, and use a 64-bit unsigned type (long with >>> in Java, uint64_t in C++). In Python, the same loop with range(64) works as is. The time stays O(1) for a fixed width. With the byte table, it becomes 8 lookups.

  • Reverse the order of the bytes, not the bits (endianness conversion).

    Take the 4 bytes of n with shifts and masks — (n >> 24) & 0xFF, (n >> 16) & 0xFF, and so on — and put them back in the opposite order. Most languages have this built in: Integer.reverseBytes in Java, __builtin_bswap32 in GCC and Clang, and int.from_bytes / to_bytes in Python. This is what network code does when converting between host order and network (big-endian) order.

Frequently asked questions

Stopping when n reaches 0 skips n's leading zeros. Those zeros must become the trailing zeros of the answer, which pushes the other bits up into the right places. With n = 2 (10), stopping early gives 01 = 1, while the correct 32-bit answer is 1073741824. A fixed 32 rounds always places every bit correctly.

In Java, >> copies the sign bit when shifting right, so a negative number would fill up with 1s; >>> always fills with 0s. In C++, shifting a signed value into or out of the top bit can be undefined behaviour, so the code works on an unsigned 32-bit copy and converts back at the end. With this problem's inputs the top bit is never set, but using the safe form avoids bugs if the limits change.

Yes: you can swap halves of the bits in 5 rounds — swap the two 16-bit halves, then the 8-bit halves inside each, then 4-bit, 2-bit and 1-bit — using masks like 0x55555555. It is clever but hard to explain and easy to get wrong in an interview. The 32-step loop is what interviewers expect; mention the mask version only as an extra.

A binary string from the language (like bin(2) or Integer.toBinaryString(2)) leaves out leading zeros, so it can be shorter than 32 characters. Reversing a short string puts the bits in the wrong positions. Padding to exactly 32 characters first makes every bit's position correct.

Bit order matters wherever data crosses a wire or a disk format. Some network protocols and checksums, such as the common CRC-32 used in Ethernet and zip files, process bits in reversed order, and bit-reversal is part of implementing them. More generally, it checks that you are comfortable with masks and shifts, which show up in IP subnet math, permission bits and feature-flag bitmaps.