문제 설명
https://leetcode.com/problems/bitwise-and-of-numbers-range
만약 주어진 입력이 아래와 같은 경우
1
2
5
7
5부터 7까지 bitwise AND 연산을 해서 나온 결과를 리턴하는 문제다. 즉
5 (0101)와 6(0110)을 Bitwise AND 연산을 하면 0100이 나온다. 0100에 7(0111)을 하면 0100이 나온다.
즉 결과는 십진수로 4가 된다.
만약 이를 5부터 7까지 Bitwise and 연산을 하면서 수행하면 아마 아래 테스트 케이스에서 Timeout error가 뜰것이다.
1
2
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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