LC 190 - Reverse Bits

Question

Reverse bits of a given 32 bits signed integer.

Example 1:

Input: n = 43261596
Output: 964176192

Explanation:

Integer	Binary
43261596	00000010100101000001111010011100
964176192	00111001011110000010100101000000

Example 2:

Input: n = 2147483644
Output: 1073741822

Explanation:

Integer	Binary
2147483644	01111111111111111111111111111100
1073741822	00111111111111111111111111111110

Constraints:

• 0 <= n <= 231 - 2
• n is even.

Follow up: If this function is called many times, how would you optimize it?

Links

Question here and solution here

Solution

concept

Use & with 1 to get the most right bit (and shift the n to the right each time): since & will only preserve that bit info and make it 0 on other bit we then move this bit to the left and do | with the output: since | will only update that bit to the answer (which initialised as 32 bit of zero) while preserving already updated answer

code

class Solution:
    def reverseBits(self, n: int) -> int:
        ans = 0
        for i in range(32):
            bit = (n >> i) & 1
            ans = ans | (bit << 31 - i)
        return ans
        
class Solution:
    def reverseBits(self, n: int) -> int:
        ans = 0
        for i in range(32):
            tmp = n%2 # get the last bit
            ans += tmp << (31 - i) # shift left by 31 - i bits
            n = n//2 # shift right by 1 bit, equivalent to n >> 1 if n is positive

        return ans       

Complexity

time: $O(1)$
space: $O(1)$