Reverse Bits of a 32-bit Number
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
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.
/*
* 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)
- How do you take the last bit of n?