두 개의 숫자 x와 y, 그리고 주어진 범위(left, right)가 있을 때, 두 숫자에서 해당 범위에 속한 모든 비트가 서로의 보수(complement) 관계인지 확인해야 합니다. 이때 비트는 오른쪽에서 왼쪽 방향으로 세며, 최하위 비트(LSB)를 첫 번째 위치로 간주한다는 점에 유의해야 합니다.
문제 이해하기
예를 들어 입력이 x = 41, y = 54, left = 2, right = 5라고 가정해 보겠습니다. 이 경우 출력은 True가 됩니다.
41과 54의 이진수 표현은 각각 101001과 110110입니다. 두 수의 2번째부터 5번째까지 비트는 x는 "1001", y는 "0110"이며, 서로 정확히 반대되는 값을 가지므로 보수 관계임을 알 수 있습니다.
해결 접근 방식
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- x와 y를 XOR 연산하여 temp 값을 구합니다.
- XOR 연산의 특성상 같은 자리의 비트가 서로 다르면 1, 같으면 0이 됩니다. 따라서 두 수가 보수 관계라면 해당 범위의 모든 비트가 1이 됩니다.
- temp의 (left, right) 범위 내 모든 비트가 1이면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
구현 코드
아래 예제 코드를 통해 더 잘 이해할 수 있습니다.
def are_all_setbits_in_range(n, left, right):
val = ((1 << right) - 1) ^ ((1 << (left - 1)) - 1)
new_value = n & val
if val == new_value:
return True
return False
def solve(x, y, left, right):
temp = x ^ y
return are_all_setbits_in_range(temp, left, right)
x = 41
y = 54
left = 2
right = 5
print(solve(x, y, left, right))입력
41, 54, 2, 5
출력
True
코드 설명
are_all_setbits_in_range 함수는 비트 마스크(mask)를 생성하는 핵심 로직을 담당합니다. ((1 << right) - 1)은 하위 right개 비트를 모두 1로 만들고, ((1 << (left - 1)) - 1)은 하위 (left-1)개 비트를 1로 만듭니다. 두 값을 XOR하면 left부터 right 위치까지만 1인 마스크가 생성됩니다.
이 마스크와 대상 숫자 n을 AND 연산한 결과가 마스크 자체와 같다면, 해당 범위의 모든 비트가 1이라는 의미입니다. 즉, 원래 두 수 x와 y의 그 범위 비트들이 모두 서로 반대(보수)였음을 확인할 수 있습니다.
이 알고리즘의 시간 복잡도는 O(1)로, 비트 연산만 사용하기 때문에 매우 효율적입니다.