C++로 두 수 사이 범위의 비트 AND(&) 값 구하기

이 문제에서는 두 개의 정수 a와 b가 주어지며, 우리의 목표는 a부터 b까지 범위에 있는 모든 숫자의 비트 AND(&) 결과를 구하는 것입니다. 즉, a & (a+1) & (a+2) & ... & (b-1) & b의 값을 계산해야 합니다.

문제 이해하기

예시를 통해 문제를 살펴보겠습니다.

입력 − a = 3, b = 8

출력 − 0

설명 − 3 & 4 & 5 & 6 & 7 & 8 = 0

단순한 해결 방법

가장 직관적인 방법은 a부터 시작하여 숫자를 하나씩 증가시키면서 b까지 모든 숫자를 차례대로 비트 AND 연산하는 것입니다. 하지만 범위가 클 경우 연산 횟수가 많아져 비효율적입니다.

더 효율적인 해결 방법

범위 내 모든 숫자를 일일이 계산하지 않고도 결과를 빠르게 구할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1단계 − b의 최하위 비트(LSB)를 반전시킵니다.

2단계 − 변경된 숫자를 a와 비교하여 범위 내에 있는지 확인합니다.

2-1단계 − 숫자가 여전히 a보다 크다면 LSB를 다시 한 번 반전시킵니다.

2-2단계 − 숫자가 a보다 작거나 같아지면 그 값이 곧 결과입니다.

알고리즘 동작 과정

예시 − a = 3, b = 8일 때,

풀이 과정 −

1단계 − b = 8은 이진수로 1000입니다. 유일하게 켜져 있는 비트인 LSB를 반전시키면 0000, 즉 0이 됩니다.

2단계 − 0은 3보다 작으므로, 결과는 0입니다.

C++ 코드 구현

이제 위 알고리즘을 코드로 구현해 보겠습니다.

#include <stdio.h>
int main(){
    long a, b;
    a = 3; b = 8;
    do{
        b -= (b & -b);
    }while(a < b);
    printf("%li", b);
}

출력 결과

0

코드에서 b & -b는 b의 가장 낮은 자리에 있는 켜진 비트(최하위 설정 비트)만을 추출하는 비트 연산 기법입니다. 이 값을 b에서 빼면 해당 비트가 꺼지게 되며, 이 과정을 b가 a보다 작거나 같아질 때까지 반복하면 범위 전체의 비트 AND 결과를 얻을 수 있습니다. 이 방법은 시간 복잡도가 O(log b)로, 단순 반복 방식보다 훨씬 효율적입니다.