Reverse Bits of a 32-bit Number

medium Math and Number Theory

Problem

Read an unsigned 32-bit integer n (0 <= n < 2^32). Reverse its 32 bits and print the result as an unsigned integer. Example: 43261596 (binary 00000010100101000001111010011100) gives 964176192.

Constraints

  • 0 <= n < 2^32

Examples

Input

43261596

Output

964176192

Solutions

Best approachTime O(32)Space O(1)

We take bits from the right end of n and push them into the result from the left, one by one. After 32 steps the order of the bits is reversed.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Reverse the 32 bits of a number.
 * Input   : One unsigned integer.
 * Output  : The reversed number.
 * Approach: Move the last bit of n to the end of the result.
 * Time    : O(32)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(long n) {
        // Step 1: The result starts as 32 zero bits. We use long, so the unsigned value fits.
        long result = 0;

        // Step 2: Repeat for all 32 bit positions.
        for (int i = 0; i < 32; i++) {
            // Step 3: Move the result one place to the left to make room.
            // Step 4: Put the last bit of n at the end of the result.
            result = (result << 1) | (n & 1);

            // Step 5: Drop the last bit of n.
            n = n >> 1;
        }
        return result;
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(solve(n));
    }
}
Hints (1)
  1. How do you take the last bit of n?