Bitwise AND of Numbers Range (python)

문제 링크 : https://leetcode.com/problems/bitwise-and-of-numbers-range/

Bitwise AND of Numbers Range - LeetCode

 

문제 )

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

 

범위 [left, right]를 나타내는 두 정수 left와 right가 주어질 때, 범위 안의 모든 정수에 대하여 bit연산 AND를 수행한 결과를 반환하세요.

 

Constraints:

• 0 <= left <= right <= 2^31 - 1

 

 

해설 )

 정수의 범위가 매우 크기 때문에 모든 정수에 대해 AND 연산을 수행하면 시간 초과 판정을 받을 수 있습니다.

AND 연산은 두 비트 중 하나라도 0이 있으면 0을 반환한다는 특징을 이해하면 더 효율적인 방법을 떠올릴 수 있습니다.

 

이 문제는 크게 2가지 경우로 나누어서 생각할 수 있습니다.

1) left와 right의 bitwise 길이가 같은 경우

2) left와 right의 bitwise 길이가 다른 경우

 

 설명하기에 앞서 left보다 right가 2배 이상 큰 경우를 생각해보겠습니다.

이 경우, Bitwise의 자릿수가 바뀌는 구간이 생기게 되고 이 구간에서 AND 연산은 반드시 0이 됩니다.

 

left = 6, right = 12 인 경우를 예로 들어 설명해보겠습니다.

 위 그림에서 6과 12 사이에 있는 7과 8의 Bitwise를 비교해보면 AND 연산 시 반드시 0이 도출됨을 알 수 있습니다.

더 정확한 설명은 두 숫자의 bitwise 자릿수가 다르면 AND 연산은 반드시 0을 반환한다로 정리할 수 있습니다.

 

 

 다음은 두 숫자의 bitwise 자릿수가 같은 경우를 살펴보겠습니다.

left = 10, right = 15로 주어졌을 때 연산 결과는 아래와 같습니다.

 가장 앞자리는 반드시 1이 됩니다.

두 번째 자리에 1이 들어가기 위해서는 left와 right 사이에 있는 모든 정수가 두 번째 자리에 1을 가져야 합니다.

즉, [12, 15] 범위에서만 AND연산 시 두 번째 자리에 1을 가질 수 있습니다.

 

 같은 원리로 4자리를 모두 검토해보면 결국 left와 right 두 숫자의 bitwise만을 비교해 결과를 얻을 수 있음을 알 수 있습니다. 앞에서부터 한 자리씩 조사하여 right와 left가 모두 1인 경우에만 해당 자릿수에 1을 가질 수 있고

right는 1이지만 left는 0인 경우 그 아래 숫자는 조사할 필요 없이 모두 0이 됨을 알 수 있습니다.

 

이를 코드로 표현하면 아래와 같습니다.

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        left, right = self.convert_to_bitwise(left), self.convert_to_bitwise(right)
        if len(left) != len(right):
            return 0

        answer = 0
        for i in range(len(right)):
            if right[i] == '1':
                if left[i] == '0':
                    break
                else:
                    answer += 2**(len(right)-1-i)
        return answer

    def convert_to_bitwise(self, num: int) -> str:
        bit = []
        while num > 0:
            if num & 1:
                bit.append('1')
            else:
                bit.append('0')
            num = num >> 1
        return ''.join(reversed(bit))