Python으로 숫자의 모든 비트가 설정되어 있는지 확인하는 방법

문제 개요

숫자 n이 주어졌을 때, 해당 숫자의 모든 비트가 1로 설정되어 있는지 확인해야 합니다.

예를 들어 입력이 n = 255라면 출력은 True가 됩니다. 255의 이진수 표현은 11111111이기 때문입니다.

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• 숫자가 0이면 False를 반환합니다.
• 숫자가 0보다 큰 동안 다음을 반복합니다.
  • 숫자가 짝수, 즉 마지막 비트가 0이면 False를 반환합니다.
  • 숫자를 오른쪽으로 1비트 시프트하여 다음 비트를 검사합니다.
• 반복문이 정상적으로 끝나면 모든 비트가 설정된 것이므로 True를 반환합니다.

핵심 아이디어는 간단합니다. 모든 비트가 1로 설정된 숫자는 반드시 홀수여야 합니다. 숫자가 짝수라면 최하위 비트(LSB)가 0이라는 뜻이므로 즉시 False를 반환하면 됩니다. number & 1 연산은 마지막 비트만 추출하고, >> 1은 숫자를 오른쪽으로 한 비트씩 밀어 다음 비트를 차례대로 검사합니다.

아래 구현 예제를 통해 더 자세히 살펴보겠습니다.

예제 코드

def solve(number):
    if number == 0:
        return False
    while number > 0:
        if (number & 1) == 0:
            return False
        number = number >> 1
    return True

n = 255
print(solve(n))

입력

255

출력

True

O(1) 최적화 기법

모든 비트가 설정된 수는 항상 2^k − 1 형태(1, 3, 7, 15, 31, ...)를 가집니다. 이 성질을 활용하면 반복문 없이 상수 시간에 답을 구할 수 있습니다.

def solve(number):
    return number != 0 and (number & (number + 1)) == 0

n & (n + 1)의 결과가 0이면 n의 모든 비트가 1로 설정되어 있다는 것을 의미합니다. 다만 n = 0인 경우도 조건을 만족하므로, 0은 별도로 제외해야 한다는 점에 유의하세요.