LeetCode #190: Reverse Bits

LeetCode Solutions

https://leetcode.com/problems/reverse-bits/description/

To solve this problem, we can use bit manipulation. We will iterate through each bit of the given integer and if it is a 1, we will set the corresponding bit in the reversed integer to 1. We can do this by shifting the bits of the original integer to the right and bitwise ORing the result with the reversed integer shifted to the left. We will repeat this process for all 32 bits.

Steps:

  1. Initialize a variable named “result” to 0
  2. Loop through all 32 bits of the input integer.
  3. If the current bit is a 1, then set the corresponding bit in the result to 1 by bitwise ORing the result with (1 shifted to the left by 31 minus the current bit position)
  4. Shift the input integer to the right by 1 bit.
  5. Shift the result to the left by 1 bit.
  6. Repeat steps 3-5 for all 32 bits.
  7. Return the result.
class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for i in range(32):
            if (n & (1 << i)) != 0:
                result |= 1 << (31 - i)
        return result

Time Complexity: The time complexity of this solution is O(1), since we are always iterating through 32 bits.

Space Complexity: The space complexity of this solution is also O(1), since we are only using a constant amount of space to store the input integer and the result.