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 uint reverseBits(uint n) {
3 uint 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}The solution follows the same bit manipulation technique. C#'s uint helps deal with unsigned integers directly, aligning with the bit patterns needed for reversal.
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 <cstdint>
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}The C++ version of this approach takes advantage of the same precomputed masks and shifts to efficiently reverse bits without needing a loop iterating over all positions, making the implementation optimized for repeated use.