The Bit Reverser

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

A firmware engineer is decoding a sensor that shifts each 32-bit register out least-significant bit first, so the integer n captured on the host has all 32 of the register's bits in reverse order. Return the register's true value as an unsigned integer.

Sometimes the answer is literally backwards.

Example 1

Input:

n = 43261596

Output:

964176192

Example 2

Input:

n = 0

Output:

0

Worked solution and explanation

What this really is

This is a fixed-width problem dressed up as bit twiddling. Anyone can flip a binary string; the skill is remembering that the register is exactly 32 bits, so the zeros above the highest set bit are real bits that have to travel to the low end. The trap is int(bin(n)[2:][::-1], 2): bin() drops leading zeros, so the width shrinks to fit the value. Feed it 1 and you get 1 back instead of 2147483648. Feed it the visible 43261596 and you get 15065253, which is the right answer shifted down six places.

Build it bit by bit

Step 1: Read the lowest bit with n & 1

The bit at the bottom of the captured value is the one that belongs at the top of the answer, so it is the first one you pull out.

Step 2: Shift result left and OR the bit in

Each new bit lands at position 0 and pushes everything already in result up one place. After 32 rounds, the first bit you read has climbed to position 31.

Step 3: Shift n right and repeat exactly 32 times

The count is the width of the register, not the length of the number. Once n runs out of set bits, the remaining rounds keep shifting zeros into result, and those shifts are what put the low bits in the right place.

Bit-by-bit reversal across a 32-bit register
def reverse_bits(n):
    result = 0
    for i in range(32):
        bit = n & 1
        result = (result << 1) | bit
        n >>= 1
    return result
Width follows the value
int(bin(n)[2:][::-1], 2) reverses only the significant bits. 1 comes back as 1, and 43261596 comes back as 15065253.
Width fixed at 32
Thirty-two shifts move every position, zeros included. 1 becomes 2147483648, and 43261596 becomes 964176192.

Common follow-up questions