Reverse Bits
Reversing the Bits of a 32-bit Unsigned Integer
In computer science, bit manipulation is a powerful tool that allows us to perform operations directly on the binary representations of numbers.
One common task is reversing the bits of a number. In this article, we will explore how to reverse the bits of a 32-bit unsigned integer and return the resulting integer.
Problem Overview
You are given a 32-bit unsigned integer n. The objective is to reverse the bits in the binary representation of n and return the resulting integer.
Input:
- A 32-bit unsigned integer
n, where0 <= n <= 2^32 - 1.
Output:
- An unsigned integer that represents the binary form of
nafter reversing its bits.
Example Walkthrough
Let’s break down an example to understand how this problem works:
Example 1
Input: n = 00000000000000000000000000010101
Output: 2818572288 (10101000000000000000000000000000)
This is the binary representation of the number 21 . When we reverse the bits of this binary number, we get:
- Original binary: 00000000000000000000000000010101
- Reversed binary: 10101000000000000000000000000000
Now, the new binary number 10101000000000000000000000000000 is equivalent to the integer 2818572288
Approach to Solve the Problem
To reverse the bits of a 32-bit unsigned integer, we can employ a bit manipulation approach. The key idea is to take each bit of the number and move it to its new position in the reversed binary string.
Here’s the step-by-step approach:
Start with the original integer.
- Initialize a result variable
reversed_numto0, which will store the final reversed result.
- Initialize a result variable
Iterate through each bit of the original number.
- For each bit in the original number, shift it to the left in the
reversed_numand move the current bit to its correct position by using bitwise operations.
- For each bit in the original number, shift it to the left in the
Use bitwise AND (
&) to isolate the current bit.- This operation helps us to extract the least significant bit (LSB) from the original number.
Shift the bits.
- After extracting the bit, shift the result left by one position, and shift the original number right by one position to prepare for the next bit.
Repeat the process for all 32 bits.
There are mainly 3 approach to solve this problem –
- Brute Force Method
- Bit Manipulation
- Bit Manipulation (Optimal)
1. Brute force
Time & Space Complexity
- Time complexity: O(1)
- Space complexity: O(1)
Python
C++
Java
JavaScript
Python
class Solution:
def reverseBits(self, n: int) -> int:
binary = ""
for i in range(32):
if n & (1 << i):
binary += "1"
else:
binary += "0"
res = 0
for i, bit in enumerate(binary[::-1]):
if bit == "1":
res |= (1 << i)
return res
C++
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
string binary = "";
for (int i = 0; i < 32; i++) {
if (n & (1 << i)) {
binary += '1';
} else {
binary += '0';
}
}
uint32_t res = 0;
for (int i = 0; i < 32; i++) {
if (binary[31 - i] == '1') {
res |= (1 << i);
}
}
return res;
}
};
Java
public class Solution {
public int reverseBits(int n) {
StringBuilder binary = new StringBuilder();
for (int i = 0; i < 32; i++) {
if ((n & (1 << i)) != 0) {
binary.append("1");
} else {
binary.append("0");
}
}
int res = 0;
String reversedBinary = binary.reverse().toString();
for (int i = 0; i < 32; i++) {
if (reversedBinary.charAt(i) == '1') {
res |= (1 << i);
}
}
return res;
}
}
JavaScript
class Solution {
/**
* @param {number} n - a positive integer
* @return {number} - a positive integer
*/
reverseBits(n) {
let binary = "";
for (let i = 0; i < 32; i++) {
if (n & (1 << i)) {
binary += "1";
} else {
binary += "0";
}
}
let res = 0;
for (let i = 0; i < 32; i++) {
if (binary[31 - i] === "1") {
res |= (1 << i);
}
}
return res >>> 0;
}
}
2. Bit Manipulation
Time & Space Complexity
- Time complexity:O(1)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for (int i = 0; i < 32; i++) {
uint32_t bit = (n >> i) & 1;
res += (bit << (31 - i));
}
return res;
}
};Java
public class Solution {
public int reverseBits(int n) {
int res = 0;
for (int i = 0; i < 32; i++) {
int bit = (n >> i) & 1;
res += (bit << (31 - i));
}
return res;
}
}
Python
class Solution:
def reverseBits(self, n: int) -> int:
res = 0
for i in range(32):
bit = (n >> i) & 1
res += (bit << (31 - i))
return resJavaScript
class Solution {
/**
* @param {number} n - a positive integer
* @return {number} - a positive integer
*/
reverseBits(n) {
let res = 0;
for (let i = 0; i < 32; i++) {
const bit = (n >>> i) & 1;
res += bit << (31 - i);
}
return res >>> 0;
}
}3. Bit Manipulation (Optimal)
- Time complexity: O(1)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t ret = n;
ret = (ret >> 16) | (ret << 16);
ret = ((ret & 0xff00ff00) >> 8) | ((ret & 0x00ff00ff) << 8);
ret = ((ret & 0xf0f0f0f0) >> 4) | ((ret & 0x0f0f0f0f) << 4);
ret = ((ret & 0xcccccccc) >> 2) | ((ret & 0x33333333) << 2);
ret = ((ret & 0xaaaaaaaa) >> 1) | ((ret & 0x55555555) << 1);
return ret;
}
};Java
public class Solution {
public int reverseBits(int n) {
int ret = n;
ret = ret >>> 16 | ret << 16;
ret = (ret & 0xff00ff00) >>> 8 | (ret & 0x00ff00ff) << 8;
ret = (ret & 0xf0f0f0f0) >>> 4 | (ret & 0x0f0f0f0f) << 4;
ret = (ret & 0xcccccccc) >>> 2 | (ret & 0x33333333) << 2;
ret = (ret & 0xaaaaaaaa) >>> 1 | (ret & 0x55555555) << 1;
return ret;
}
}
Python
class Solution:
def reverseBits(self, n: int) -> int:
res = n
res = (res >> 16) | (res << 16) & 0xFFFFFFFF
res = ((res & 0xff00ff00) >> 8) | ((res & 0x00ff00ff) << 8)
res = ((res & 0xf0f0f0f0) >> 4) | ((res & 0x0f0f0f0f) << 4)
res = ((res & 0xcccccccc) >> 2) | ((res & 0x33333333) << 2)
res = ((res & 0xaaaaaaaa) >> 1) | ((res & 0x55555555) << 1)
return res & 0xFFFFFFFF
JavaScript
class Solution {
/**
* @param {number} n - a positive integer
* @return {number} - a positive integer
*/
reverseBits(n) {
let ret = n >>> 0;
ret = (ret >>> 16) | (ret << 16);
ret = ((ret & 0xff00ff00) >>> 8) | ((ret & 0x00ff00ff) << 8);
ret = ((ret & 0xf0f0f0f0) >>> 4) | ((ret & 0x0f0f0f0f) << 4);
ret = ((ret & 0xcccccccc) >>> 2) | ((ret & 0x33333333) << 2);
ret = ((ret & 0xaaaaaaaa) >>> 1) | ((ret & 0x55555555) << 1);
return ret >>> 0;
}
}
