LESSON 458 OF 501 · BIT MANIPULATION

Reverse Bits in Java

Practice O(1)

You are given a number n, written in binary with exactly 32 bits (leading zeros included).

Reverse the order of those 32 bits: the last bit becomes the first, the second to last becomes the second, and so on. Return the number that the reversed bits form.

Example 1:

Input: n = 43261596
Output: 964176192
Explanation: 43261596 in 32 bits is 00000010100101000001111010011100.
Reversed, the bits are 00111001011110000010100101000000, which is 964176192.

Example 2:

Input: n = 1
Output: 2147483648
Explanation: 1 is 00000000000000000000000000000001.
Reversed, its only 1 bit moves to the front: 10000000000000000000000000000000, which is 2³¹ = 2147483648.

Example 3:

Input: n = 4294967293
Output: 3221225471
Explanation: 4294967293 is 11111111111111111111111111111101.
Reversed, the bits are 10111111111111111111111111111111, which is 3221225471.

Constraints:

0 <= n <= 2³² - 1
The answer is also between 0 and 2³² - 1.
Numbers this large don't fit in a 32-bit signed integer, so n and the answer use a type that holds 2³² - 1: the one in the starter code.

Note:

Your algorithm should run in O(1) time, one step for each of the 32 bits, and use O(1) extra space.

Take the bits of n one at a time from its right end: n AND 1 is the last bit, and shifting n one place right drops it, so the next bit becomes the last one. Where should each bit you take go in the answer?

Build the answer in result, starting from 0. In each round, shift result one place left, which leaves a 0 at its right end, and put the bit you took there with OR. Do it exactly 32 times, even after n has become 0: the first bit you took then ends up in the first of the 32 places.

The loop always runs 32 times, whatever n is: O(1) time.
We keep two numbers, so the extra space is O(1).

STEP 1 OF 5

Guided

Ctrl + Enter to check