Reverse Bits

Patrick Leaton

Published: March 16, 2021, 3:52 p.m.

Problem Description

Reverse bits of a given 32 bits unsigned integer.

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimize it?

Example 1:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Constraints:

The input must be a binary string of length 32

Description taken from https://leetcode.com/problems/reverse-bits/.

Problem Solution

#O(1) Time, O(1) Space

class Solution:

def reverseBits(self, n: int) -> int:

result, power = 0, 31

while n is not 0:

result += (n & 1) << power

n >>= 1

power -= 1

return result

Problem Explanation

Since we are given a problem that requires isolating and moving bits, that is an indication that we will be using bit manipulation.

We can solve this problem by doing bit-by-bit operations, specifically grabbing the rightmost bit from the input number and placing that as the leftmost bit in the output number. Since we are given a thirty-two-bit integer, we can keep that in mind when setting the position of our bits in our output binary number and just decrement the value from thirty-two.

Let's initialize our result to zero and our power index to thirty-one. Binary numbers' least significant bit is 2^0, and its most significant bit is 2^31, a range of thirty-two bits. The beginning index is zero like they are in arrays.

result, power = 0, 31

While our input number still has bits we need to shift, we will continue processing it.

while n is not 0:

Let's use the AND operator on our current input number with the number one. This will return a one if the least significant, rightmost bit from the input number that we are looking at is one. Otherwise, it will return zero.

From there, we will grab that bit and place it within whichever power index we are currently at within the output number. Initially, it will be the thirty-second bit, then the thirty-first, etc.

We are pulling bits from the input number, going from the least significant bit to the most significant bit, right to left.

We are then placing those bits into the output number, ordering them from the most significant bit to the least significant bit, from left to right. That is how we are reversing the bits.

result += (n & 1) << power

After we have placed a bit, we will shift the input number to the right so that we can choose and pull the next least significant bit within the next iteration, the bit to the left of the current one.

n >>= 1

We will also decrement our power index so that we can push the next most significant bit into the index to the right of the current one.

power -= 1

Once our input integer is zero or all power indices have been filled, we will return our result.

return result