876478. Reverse Bits
Reverse Bits
Slug: reverse-bits--142401 Difficulty: Easy Id: 876478 Topic Tags: Bit Magic
Summary
The "Reverse Bits" problem involves reversing the bits of a given integer. This is a fundamental problem in computer science that requires an understanding of bitwise operations and bit manipulation.
Detailed Explanation
To solve this problem, we can use a simple algorithm that iterates over the bits of the input number, shifting them to the left (to create space) and then flipping them using the XOR operator (^). This approach ensures that the least significant bit becomes the most significant bit, effectively reversing the order of the bits.
Here's a step-by-step breakdown of the solution:
- Initialize an integer variable
resultto 0. - Iterate over the bits of the input number from right to left (least significant bit to most significant bit).
- For each bit, shift
resultone position to the left using the left shift operator (<<). - Flip the current bit using the XOR operator (^) and assign it to
result. - Repeat steps 2-4 until all bits of the input number have been processed.
- The final value of
resultis the reversed integer.
Time complexity: O(log n), where n is the input integer, since we're iterating over its bits. Space complexity: O(1), as we only use a constant amount of space to store the result and temporary variables.
Optimized Solutions
Java
public int reverseBits(int n) {
int result = 0;
for (int i = 0; i < 32; i++) { // assuming 32-bit integer
result <<= 1;
result ^= (n & 1);
n >>= 1;
}
return result;
}