파이썬으로 두 숫자가 서로 1의 보수 관계인지 확인하는 방법

문제 이해

두 개의 숫자 x와 y가 주어졌을 때, 이들 중 하나가 다른 하나의 1의 보수(1's complement)인지 판별하는 문제입니다.

여기서 1의 보수란 이진수의 모든 비트를 반전시키는 것을 의미합니다. 즉, 0은 1로, 1은 0으로 뒤집는 연산입니다.

예를 들어 입력이 x = 9, y = 6이라면 결과는 True가 됩니다. 9의 이진 표현은 1001이고, 6의 이진 표현은 0110으로, 각 비트가 정확히 서로 반대이기 때문입니다.

해결 전략

이 문제는 XOR 연산의 성질을 활용하면 매우 간단하게 해결할 수 있습니다. 어떤 수와 그 수의 보수를 XOR하면 모든 비트가 1인 값이 나옵니다. 따라서 다음 단계를 따릅니다.

• z = x XOR y를 계산합니다.
• z의 모든 비트가 1로 설정되어 있으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

모든 비트가 1인지 확인하는 방법

모든 비트가 1로 채워진 수(예: 7 = 111, 15 = 1111)는 항상 2^k − 1 형태입니다. 이런 수에 1을 더하면 자리올림이 연쇄적으로 발생해 모든 비트가 0이 되므로, (n + 1) & n == 0 조건을 만족합니다. 이 성질을 이용해 한 번의 비트 연산으로 확인할 수 있습니다.

구현 예제

def all_one(n):
    if n == 0:
        return False
    # n+1과 n을 AND하면 0이 되려면 n의 모든 비트가 1이어야 함
    if ((n + 1) & n) == 0:
        return True
    return False

def solve(x, y):
    # x와 y가 서로 보수라면 x ^ y의 모든 비트는 1이 됨
    return all_one(x ^ y)

x = 9
y = 6
print(solve(x, y))

실행 결과

입력:

9, 6

출력:

True

복잡도 분석

• 시간 복잡도: O(1) — XOR 연산과 AND 연산은 상수 시간에 수행됩니다.
• 공간 복잡도: O(1) — 추가 메모리 없이 몇 개의 변수만 사용합니다.

XOR과 비트 마스킹만으로 보수 관계를 빠르게 판별할 수 있는, 비트 연산의 강력함을 보여주는 대표적인 예제입니다.