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).
1#include <stdint.h>
2
3uint32_t reverseBits(uint32_t n) {
4 n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1);
5 n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);
6 n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
7 n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8);
8 n = ((n >> 16) & 0x0000FFFF) | ((n & 0x0000FFFF) << 16);
9 return n;
10}This solution involves swapping bits in progressively larger chunks. It uses binary masks (e.g., 0x55555555, 0x33333333) to select and swap specific bits. This method is efficient as it reduces the number of operations required, making it faster for multiple invocations.