[Leet Code풀이] 201. Bitwise AND of Numbers Range

문제 설명

https://leetcode.com/problems/bitwise-and-of-numbers-range

만약 주어진 입력이 아래와 같은 경우

5
7

5부터 7까지 bitwise AND 연산을 해서 나온 결과를 리턴하는 문제다. 즉

5 (0101)와 6(0110)을 Bitwise AND 연산을 하면 0100이 나온다. 0100에 7(0111)을 하면 0100이 나온다.

즉 결과는 십진수로 4가 된다.

만약 이를 5부터 7까지 Bitwise and 연산을 하면서 수행하면 아마 아래 테스트 케이스에서 Timeout error가 뜰것이다.

600000000
2147483645

저 TC를 보면서 깨달은 것은 두가지가 있다.

첫번째로 bitwise를 순차적으로 하면서 0이 나온다면, 그 뒤부터는 어차피 bitwise AND를 해도 0이 된다.

두번째로 순차적으로 bitwise 연산을 하다가 000010000 이렇게 끝나는게 있다면 여기에 000010001, 000010010, 000010011 … 모두 bitwise 연산을 해도 000010000이 된다. 그러므로 000010000 와 같이 0으로 끝나면 그 다음 계산은 000100000 부터 하면된다. 그게 아니라면 1씩 증가시켜 가면서 bitwise AND 연산을 진행한다.

이를 코드로 구현하면 아래와 같다.

풀이

Runtime: 122 ms, faster than 48.32% of Python3 online submissions for Bitwise AND of Numbers Range. Memory Usage: 13.8 MB, less than 97.86% of Python3 online submissions for Bitwise AND of Numbers Range.

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        result = left
        i = result
        
        while (i <= right):
            result &= i
            
            # 한번 0 나오면 그냥 0
            if result == 0:
                return 0
            
            # 뒤에 이진수로 000010000 이렇게 끝나는게 있다면 000010001, 000010010, 000010011 ... 모두 000010000
            # 그러므로 000010000 와 같이 0으로 끝나면 그 다음 계산은 000100000 부터 하면된다.
            # 그게 아니라면 1씩 증가시켜 가면서 & 연산 진행
            ind = -1
            target = 1
            if int(bin(result)[ind]) == 0:
                while (int(bin(result)[ind]) == 0 and result + target <= right):
                    ind -= 1
                    target = target << 1
                i = result + target
            else:
                i += 1
                
        return result