Problem statement
Reverse bits of a given 32 bits unsigned integer.
Link to problem
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.
Solutions
Approach 1: Shifting
Pretty simple approach that I thought of in paint. You basically shift right for the given number and shift left for your result so you can accomodate the bits.
Pseudocode
set result = 0
begin loop until 32
left shift result by 1
add number % 2 to result
right shift number by 1
return result
For example: 1011
result number % 2 number >> 1
1 1011 % 2 = 1 101
11 101 % 2 = 1 10
110 10 % 2 = 0 1
1101 1 % 2 = 1 -
Implementation in Rust
fn reverse_bits(mut x: u32) -> u32 {
let mut result: u32 = 0;
for i in 0..32 {
result = result << 1;
result = result + (x % 2);
x = x >> 1;
}
result
}
Time Complexity: $O(1)$
Runtime on LeetCode: $0$ms