LeetCode 190: Reverse Bits

link

Two pointers

Starting with the two pointers (right, left) = (31, 0), keep swapping towards the center.

Time: \mathcal{O}(1), space: \mathcal{O}(1).

class Solution:
    def get_bit_at(self, pos, x):
        return (x >> pos) & 1
    
    def set_bit_at(self, pos, val, x):
        if val == 0:
            return x & ~(1 << pos)
        else:
            return x | (1 << pos)

    def reverseBits(self, n: int) -> int:
        left, right = 0, 31
        while left < right:
            left_val = self.get_bit_at(left, n)
            right_val = self.get_bit_at(right, n)
            if left_val != right_val:
                n = self.set_bit_at(left, right_val, n)
                n = self.set_bit_at(right, left_val, n)
            left += 1
            right -= 1
        
        return n

Leave a comment