Reverse Bits

The problem

You are given a 32-bit unsigned number number. Reverse the order of its 32 bits: bit 0 becomes bit 31, bit 1 becomes bit 30, and so on. Return the number those reversed bits make.

Example 1

Input: number = 10555190

Output: 1827702016

In hex, 0x00A10F36 becomes 0x6CF08500. The picture shows both, a byte per row. Leading zeros count: the 8 zeros on top move to the bottom.

input 31–24

00000000

input 23–16

10100001

input 15–8

00001111

input 7–0

00110110

output 31–24

01101100

output 23–16

11110000

output 15–8

10000101

output 7–0

00000000

Example 2

Input: number = 1

Output: 2147483648

The only 1 is bit 0. It moves to bit 31, which is 2³¹.

Example 3

Input: number = 4294967295

Output: 4294967295

All 32 bits are 1, so the mirror image looks the same.

Constraints

• 0 ≤ number ≤ 2³² − 1, and number always has exactly 32 bits, leading zeros included.
• Below, b is the number of bits (32).

Clarifying questions

Do leading zeros count?

Yes. All 32 bits are reversed, so the zeros on top end up at the bottom.

How does Java or C# pass an unsigned 32-bit number?

Java has no unsigned int, so it passes the same 32 bits as an int, which may look negative. Use >>> to shift in zeros. C# can use uint.

What if the function is called many times?

That is the follow-up. The mask version does a fixed 5 steps with no loop. A table of reversed bytes also works.

Spot the pattern

The task moves bits around, not values. That is bit manipulation: number & 1 reads the lowest bit, shifts move bits, and a mask like 0xFF00FF00 picks out a group of bits at once.

Solutions

Bit by bitO(b)Swap blocksO(log b)

Show all

This problem has two approaches. Turning number into a string, reversing it and parsing it back is the same bit-by-bit idea with extra memory.

Bit by bit O(b)

The idea

Build the answer result one bit at a time. Each run, shift result left to make room, put the lowest bit of number into that room, then shift number right to drop that bit. Do this exactly 32 times, even if number becomes 0 early, so that leading zeros are counted.

The first bit taken from number is bit 0. It gets shifted left 31 more times, so it ends up as bit 31.

Walkthrough

number 31–24

00000000

number 23–16

10100001

number 15–8

00001111

number 7–0

00110110

result 31–24

00000000

result 23–16

00000000

result 15–8

00000000

result 7–0

00000000

runs

0

1. result = 0
2. for _ in range(32):
3. result = (result << 1) | (number & 1)
4. number >>= 1
5. return result

number = 10555190 (0x00A10F36). Take the lowest bit of number and push it onto the right of result, 32 times. The first bit taken ends up highest.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Bit by bit: push each bit of number onto the right of result.
    // 32 runs, even after number is 0: O(b) time, O(1) memory.
    public int reverseBits(int number) {
        int result = 0;
        // Run all 32 times, so the leading zeros move too.
        for (int k = 0; k < 32; k++) {
            result = (result << 1) | (number & 1);
            number >>>= 1;
        }
        return result;
    }
}

Big O

Time O(b)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines shift result, read one bit, and shift number. That is 1 step. They sit inside one loop.

   1. result = 0
   2. for _ in range(32):
   3. result = (result << 1) | (number & 1)
   4. number >>= 1
   5. return result

2. 2 Count the runs on Example 1

   The loop runs once per bit of number. The table groups the runs by byte.

   8 + 8 + 8 + 8 = 32 runs.

   bits of number	0–7	8–15	16–23	24–31
   runs	8	8	8	8

   total

   8 + 8 + 8 + 8 = 32 runs

3. 3 Write the count for any n

   The loop runs exactly once per bit, for every input:

   b runs, and b = 32

   Check it with Example 1: 32 runs. Example 2 also takes 32, even though most of its bits are 0.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is b. Since b is fixed at 32, you can also call it O(1). Saying O(b) shows how it would grow with a wider number.

   So the time is O(b).

5. S Space: count the extra memory the same way

   The code keeps result and number. The space is O(1).

   resultnumber

Swap blocks O(log b)

The idea

Reversing a list is the same as swapping its two halves, then reversing each half. Do that to the bits, but for every block at once:

1. Swap the two blocks of 16 bits.
2. In each 16, swap the two blocks of 8.
3. In each 8, swap the two blocks of 4.
4. Then blocks of 2, then single bits.

A mask picks out the high block of every pair, and another picks the low block. Shift one right and the other left by the block size, and join them with |. One line swaps every pair.

Walkthrough

number 31–24

00000000

number 23–16

10100001

number 15–8

00001111

number 7–0

00110110

1. number = ((number >> 16) | (number << 16)) & 0xFFFFFFFF
2. number = ((number & 0xFF00FF00) >> 8) | ((number & 0x00FF00FF) << 8)
3. number = ((number & 0xF0F0F0F0) >> 4) | ((number & 0x0F0F0F0F) << 4)
4. number = ((number & 0xCCCCCCCC) >> 2) | ((number & 0x33333333) << 2)
5. number = ((number & 0xAAAAAAAA) >> 1) | ((number & 0x55555555) << 1)
6. return number

number = 0x00A10F36. Instead of moving one bit at a time, swap the two halves, then the halves of each half, and so on. Five swaps reverse all 32 bits.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Swap blocks: swap the halves of 16 bits, then 8, 4, 2 and 1.
    // log2(32) = 5 steps: O(log b) time, O(1) memory.
    public int reverseBits(int number) {
        // >>> shifts in zeros, because Java has no unsigned int.
        number = (number >>> 16) | (number << 16);
        // Each mask picks the high or the low block of every pair.
        number = ((number & 0xFF00FF00) >>> 8) | ((number & 0x00FF00FF) << 8);
        number = ((number & 0xF0F0F0F0) >>> 4) | ((number & 0x0F0F0F0F) << 4);
        number = ((number & 0xCCCCCCCC) >>> 2) | ((number & 0x33333333) << 2);
        number = ((number & 0xAAAAAAAA) >>> 1) | ((number & 0x55555555) << 1);
        return number;
    }
}

Big O

Time O(log b)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each lit line does two masks, two shifts and one | on a whole 32-bit word. The processor does each of those in one go, so each line is 1 step. There is no loop.

   1. number = ((number >> 16) | (number << 16)) & 0xFFFFFFFF
   2. number = ((number & 0xFF00FF00) >> 8) | ((number & 0x00FF00FF) << 8)
   3. number = ((number & 0xF0F0F0F0) >> 4) | ((number & 0x0F0F0F0F) << 4)
   4. number = ((number & 0xCCCCCCCC) >> 2) | ((number & 0x33333333) << 2)
   5. number = ((number & 0xAAAAAAAA) >> 1) | ((number & 0x55555555) << 1)
   6. return number

2. 2 Count the runs on Example 1

   The block size starts at 16 and halves each step until it is 1.

   5 steps.

   step	1	2	3	4	5
   block size	16	8	4	2	1

   total

   5 steps

3. 3 Write the count for any n

   The block size halves from b / 2 down to 1, so the number of steps is how many times b can be halved:

   log₂ b steps, and log₂ 32 = 5

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is log b. For b = 32 that is 5 steps against 32 runs. Both are O(1) for a fixed 32 bits, but this one has no loop and no branch.

   So the time is O(log b).

5. S Space: count the extra memory the same way

   The code changes number in place and keeps nothing else. The space is O(1).

   number

Common mistake

Stopping when number becomes 0

A loop like while number: stops after the highest 1 bit. For number = 1 it runs once and returns 1, but the answer is 2³¹. The bit-by-bit loop must run all 32 times, so the leading zeros are moved too.

Tested at the limits

2,000 random 32-bit numbers, with 0, single bits, the top bit and runs of ones mixed in. Bit by bit and swap blocks gave the same answer every time, and matched a check that reverses the binary text.

Largest inputs	Result
One 32-bit number with ones at both ends. Swap blocks.	Under 0.001 s, and under 0.001 MB of extra memory: it changes number in place.
Every single bit, all 32 of them. Both approaches.	Each bit landed in its mirror place, the strongest check for the masks.