[2024] day 53. Leetcode 201. Bitwise AND of Numbers Range

gunny·2024년 2월 21일

201. Bitwise AND of Numbers Range 201. Bitwise AND of Numbers Range python leetcode 201. Bitwise AND of Numbers Range leetcode 201. Bitwise AND of Numbers Range python

코딩테스트

목록 보기

366/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 2월 21일 (수)
Leetcode daily problem

201. Bitwise AND of Numbers Range

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

Problem

2개의 left, right 정수가 주어질 때
left와 right 정수 사이에 있는 모든 수의 비트단위로 AND 연산한 값을 반환한다.

AND 연산 : 두 숫자를 각각 같은 자리수에 있는 숫자끼리 곱함. 예를 들어, 1과 1을 AND 연산하면 1이 되고, 그 외의 경우에는 모두 0이 됨

Solution

bit 연산 / shift 연산

해당 문제는 비트 단위에서 숫자들은 연산한다.
left가 5, right가 7이라고 한다면
해당 범위의 숫자인 5,6,7를 모두 이진 표현한다면
5(10) : 101(2)
6(10) : 110(2)
7(10) : 111(2) 가 되고 이를 and 연산하면 100(2)이 된다.

그러나 case 3과 같이
left가 1이고 right가 2147483647일 때, 이 범위 내의 모든 숫자를 비트 단위 AND 연산하여 결과를 구할 때, 매우 큰 범위의 숫자이기 때문에 각 숫자를 이진수로 변환하여 비트 단위 연산을 하는 것은 효율적이지 않다.

이러한 문제에서 고려해야 할 점은 가장 큰 숫자와 가장 작은 숫자를 비트 단위로 비교했을 때, 가장 왼쪽 비트부터 시작하여 처음으로 다른 비트가 나오는 순간 그 이후의 비트들은 AND 연산 시에 모두 0이 된다는 것이다.

즉, left와 right 값이 같을 때까지 오른쪽으로 시프트하면서 공통된 부분을 찾아야 한다.

위의 case 3에서의 left, right를 이진수로 표현한다면
left: 00000000000000000000000000000001 (1)
right: 01111111111111111111111111111111 (2147483647)

이다.

위의 경우, 왼쪽부터 오른쪽으로 비교했을 때, 가장 왼쪽 비트부터 0과 1로 시작하고 이후에는 모두 1로 채워진 형태이다. 이러한 경우에는 가장 왼쪽 비트 이후의 비트들은 AND 연산 시에 항상 0이 된다.

따라서, left와 right 사이의 모든 숫자를 AND 연산한 결과는 0이다. 이러한 문제의 경우, 단순히 범위의 시작점과 끝점을 AND 연산하는 것으로 결과를 구할 수 있다.

정리하자면

(1) 가장 작은 숫자(left)와 가장 큰 숫자(right) 사이에 공통된 비트를 찾는다.
(2) 공통된 비트 이후에 나타나는 비트들은 AND 연산 시에 항상 0이 된다.
(3) 우리는 공통된 비트 이후의 비트들을 모두 0으로 만들어준다.
(4) 이를 위해 두 숫자를 오른쪽으로 시프트하면서, 두 숫자가 같아질 때까지 진행한다.
(5) 시프트한 만큼 최종 이동한 가장 작은 숫자(left)를 왼쪽으로 시프트하고 해당 값을 반환한다.

Code


class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        shift = 0
        while left <right:
            left >>= 1
            right >>= 1
            shift +=1
        
        return left << shift