In this approach, we utilize bitwise operations to reverse the bits. We iterate through each bit of the number from the least significant bit (LSB) to the most significant bit (MSB), shifting the resultant bits to the left and using the bitwise OR operation to set the bits in the reversed order.
Time Complexity: O(1) because the operation involves a fixed number of 32 iterations, and each operation within the loop is O(1).
Space Complexity: O(1) since we only use a constant amount of additional space for variables.
1public class Solution {
2 public int reverseBits(int n) {
3 int result = 0;
4 for (int i = 0; i < 32; i++) {
5 result = (result << 1) | (n & 1);
6 n >>>= 1;
7 }
8 return result;
9 }
10}This Java implementation uses a similar approach with the difference in using '>>>' for unsigned right shift, as Java doesn't have an unsigned int type.
This approach could be optimized by precomputing masks that handle groups of bits. This reduces the need for iterating through each bit and instead processes larger chunks of bits through bit manipulation techniques.
Time Complexity: O(1).
Space Complexity: O(1).
1public class Solution {
2 public int reverseBits(int n) {
3 n = ((n >>> 1) & 0x55555555) | ((n & 0x55555555) << 1);
4 n = ((n >>> 2) & 0x33333333) | ((n & 0x33333333) << 2);
5 n = ((n >>> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4);
6 n = ((n >>> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8);
7 n = ((n >>> 16) & 0x0000ffff) | ((n & 0x0000ffff) << 16);
8 return n;
9 }
10}Java applies the same mask and shift strategy with '>>>' for unsigned right shifts, optimizing the bit reversal process through constant time operations despite Java not having native unsigned integers.