Description
Reverse bits of a given 32 bits unsigned integer.
Note:
- Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
- In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above, the input represents the signed integer
-3and the output represents the signed integer-1073741825.
Examples:
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.Solution in Python
Python
class Solution:
def reverseBits(self, n: int) -> int:
# Initialize the result to 0
result = 0
# Iterate over all 32 bits of the input integer
for i in range(32):
# Extract the least significant bit (rightmost bit) of n
bit = n & 1
# Shift the result to the left to make space for the new bit
result = (result << 1) | bit
# Shift the input n to the right to process the next bit
n >>= 1
# Return the reversed bit integer
return resultExplanation
- Initialization:
result = 0: Start with aresultvariable initialized to0. This variable will accumulate the reversed bits.
- Iterating Over 32 Bits:
- The loop runs 32 times because we are dealing with a 32-bit integer. Each iteration processes one bit of the input integer
n.
- The loop runs 32 times because we are dealing with a 32-bit integer. Each iteration processes one bit of the input integer
- Extracting the Least Significant Bit:
bit = n & 1: Use bitwise AND with1to extract the least significant bit (LSB) ofn. This isolates the rightmost bit.
- Shifting the Result:
result = (result << 1) | bit: Shift the bits inresultto the left by 1 position to make space for the new bit. Then, use bitwise OR to add the extracted bit toresult.
- Shifting the Input Integer:
n >>= 1: Shiftnto the right by 1 position to move the next bit into the LSB position. This preparesnfor the next iteration of the loop.
- Return the Reversed Integer:
- After processing all 32 bits,
resultcontains the reversed bit sequence. The function returns this value.
- After processing all 32 bits,
Solution in Javascript
JavaScript
/**
* @param {number} n - a positive integer
* @return {number} - a positive integer
*/
var reverseBits = function(n) {
// Initialize the result to 0
let result = 0;
// Iterate over all 32 bits of the input integer
for (let i = 0; i < 32; i++) {
// Extract the least significant bit (rightmost bit) of n
let bit = n & 1;
// Shift the result to the left to make space for the new bit
result = (result << 1) | bit;
// Shift the input n to the right to process the next bit
n >>>= 1; // Use >>> to ensure unsigned right shift
}
// Return the reversed bit integer
return result >>> 0; // Ensure the result is treated as an unsigned integer
};Solution in Java
Java
public class Solution {
// You need to treat n as an unsigned value
public int reverseBits(int n) {
// Initialize the result to 0
int result = 0;
// Iterate over all 32 bits of the input integer
for (int i = 0; i < 32; i++) {
// Extract the least significant bit (rightmost bit) of n
int bit = n & 1;
// Shift the result to the left to make space for the new bit
result = (result << 1) | bit;
// Shift the input n to the right to process the next bit
n >>>= 1; // Use >>> to ensure unsigned right shift
}
// Return the reversed bit integer
return result;
}
}Solution in C#
C#
public class Solution
{
public uint reverseBits(uint n)
{
uint result = 0; // Initialize the result to 0.
// Loop through all 32 bits of the integer.
for (int i = 0; i < 32; i++)
{
// Left shift the result by 1 bit to make space for the next bit.
result <<= 1;
// Extract the least significant bit (rightmost) of n and add it to result.
result |= (n & 1);
// Right shift n by 1 bit to process the next bit in the next iteration.
n >>= 1;
}
return result; // Return the reversed bits as the final result.
}
}