Python으로 두 숫자가 한 비트 위치에서만 다른지 확인하는 방법

문제 개요

두 개의 숫자 x와 y가 주어졌을 때, 이 두 숫자가 정확히 한 개의 비트 위치에서만 서로 다른지 확인하는 문제입니다.

예를 들어 입력이 x = 25, y = 17이라면 출력은 True가 됩니다. 25는 이진수로 11001, 17은 이진수로 10001이며, 두 숫자는 한 비트 위치만 다르기 때문입니다.

해결 접근 방법

이 문제는 XOR 연산과 비트 카운트를 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. XOR 연산은 두 비트가 서로 다를 때만 1을 반환하므로, x와 y를 XOR한 결과에서 1로 설정된 비트의 개수를 세면 두 숫자가 다른 비트 위치의 개수를 바로 알 수 있습니다.

구체적인 풀이 단계는 다음과 같습니다.

1단계: z = x XOR y를 계산합니다. z에는 두 숫자가 서로 다른 비트 위치에만 1이 설정됩니다.
2단계: z에서 값이 1로 설정된 비트의 개수를 셉니다.
3단계: 설정된 비트의 개수가 정확히 1이라면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

예제 코드

def bit_count(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

def solve(x, y):
    return bit_count(x ^ y) == 1

x = 25
y = 17
print(solve(x, y))

입력

25, 17

출력

True

동작 원리 상세 설명

위 코드에서 bit_count 함수는 숫자 n을 오른쪽 시프트(>>=)하면서 가장 오른쪽 비트(n & 1)가 1인지 확인하여 설정된 비트의 개수를 계산합니다.

실제 실행 과정을 살펴보면 다음과 같습니다.

x = 25 → 이진수 11001
y = 17 → 이진수 10001
x ^ y = 01000 (십진수 8)
설정된 비트 개수 = 1 → True 반환

더 간결한 대안: 내장 함수 활용

파이썬에서는 별도의 함수를 작성하지 않고도 내장 기능으로 같은 결과를 얻을 수 있습니다.

def solve(x, y):
    return bin(x ^ y).count('1') == 1

# 파이썬 3.10 이상에서는 int.bit_count() 사용 가능
def solve_v2(x, y):
    return (x ^ y).bit_count() == 1

bin() 함수는 정수를 '0b' 접두사가 붙은 이진 문자열로 변환하며, count('1')로 1의 개수를 셉니다. 또한 파이썬 3.10부터는 int.bit_count() 메서드를 제공하여 더욱 직관적으로 비트 수를 구할 수 있습니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(log n)입니다. 비트 카운트 과정에서 숫자의 비트 수만큼 반복하기 때문입니다. 공간 복잡도는 O(1)로 추가 메모리를 거의 사용하지 않습니다.