class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        # Python has a dumb "bug" where right.bit_length() == 0 when right == 0
        if right == 0:
            return 0

        ans = right
        for i in range(right.bit_length()):
            cur = self.biggest_less_than_with_bit_zeroed(right, i)
            # print(bin(cur)[2:].rjust(right.bit_length(), '0'), right.bit_length())
            if cur >= left:
                ans &= cur
        return ans

    def biggest_less_than_with_bit_zeroed(self, num: int, i: int) -> int:
        """Returns the biggest integer less than num where bit i is zero"""

        # If the bit is already 0, then num is the largest.
        if ((1 << i) & num) == 0:
            return num

        num_bits = num.bit_length()

        mask = (1 << num_bits) - 1
        right_mask = (1 << (i + 1)) - 1

        ans = num - (num & right_mask)
        ans += right_mask >> 1
        return ans