파이썬으로 주어진 범위 내 모든 숫자의 비트 AND(Bitwise AND) 구하기

문제 이해

두 값 start와 end가 주어졌을 때, [start, end] 범위(양 끝값 포함)에 속한 모든 숫자의 비트 AND 연산 결과를 구하는 것이 목표입니다.

예를 들어 start = 8, end = 12가 입력으로 주어지면 출력은 8이 됩니다. 그 이유는 다음과 같습니다.

8은 이진수로 1000
9는 이진수로 1001
10은 이진수로 1010
11은 이진수로 1011
12는 이진수로 1100

따라서 1000 AND 1001 AND 1010 AND 1011 AND 1100의 결과는 1000, 즉 십진수로 8입니다.

알고리즘 접근 방법

이 문제는 상위 비트부터 하위 비트까지 차례대로 검사하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

범위 내 숫자의 개수를 n = end - start + 1로 계산합니다.
상위 비트(b = 31부터 0까지)를 순회하면서, 해당 비트 값 2^b가 n보다 크거나 같고 start와 end 양쪽 모두에서 설정되어 있다면, 범위 내 모든 숫자가 해당 비트를 공유한다는 의미이므로 결과에 더합니다.
2^b < n이 되는 순간, 그보다 낮은 비트들은 범위 안에서 반드시 변하게 되므로 더 이상 검사할 필요가 없습니다.

단계별 풀이

n := end - start + 1 (범위 내 숫자 개수)
x := 0 (결과값 초기화)
b를 31부터 0까지 1씩 감소시키며 반복:
- 만약 2^b < n이면 반복 종료
- 만약 2^b AND start AND end가 0이 아니라면, x := x + 2^b
x 반환

파이썬 구현 예제

def solve(start, end):
   n = end - start + 1
   x = 0
   for b in range(31, -1, -1):
      if (1 << b) < n:
         break
      if (1 << b) & start & end:
         x += 1 << b
   return x

start = 8
end = 12
print(solve(start, end))

입력

start = 8, end = 12

출력

복잡도 분석

시간 복잡도: O(1) — 최대 32비트만 검사하므로 상수 시간에 동작합니다.
공간 복잡도: O(1) — 추가 메모리를 거의 사용하지 않습니다.

참고: 대안적인 접근 방법

같은 문제는 start와 end의 공통 접두사(common prefix)를 찾는 방식으로도 해결할 수 있습니다. 두 수를 오른쪽으로 시프트하면서 값이 같아질 때까지 반복한 뒤, 다시 왼쪽으로 시프트하여 되돌리면 범위의 비트 AND 결과를 얻을 수 있습니다.

def solve_prefix(start, end):
   shift = 0
   while start != end:
      start >>= 1
      end >>= 1
      shift += 1
   return start << shift

두 방법 모두 O(1) 시간 복잡도를 가지며, 실무에서는 코드 가독성에 따라 선택하면 됩니다.