범위 [m, n]이 주어졌을 때(단, 0 ≤ m ≤ n ≤ 2147483647), 이 범위에 포함된 모든 숫자의 비트 AND(bitwise AND) 연산 결과를 구하는 문제입니다. 예를 들어 범위가 [5, 7]이라면, 5 AND 6 AND 7의 결과는 4가 됩니다.
문제 접근 방법
범위 내 모든 숫자를 하나씩 AND 연산하면 시간이 오래 걸릴 수 있습니다. 대신 다음과 같은 효율적인 방법을 사용할 수 있습니다.
- 카운터 변수 i를 0으로 초기화합니다.
- m과 n이 같아질 때까지 두 값을 각각 오른쪽으로 1비트씩 시프트하고, 그때마다 i를 1씩 증가시킵니다.
- 두 값이 같아지면, 남은 공통 접두사(prefix)인 m을 왼쪽으로 i번 시프트하여 반환합니다.
이 방법이 동작하는 이유는, 범위 [m, n] 내 모든 수의 공통 비트는 m과 n의 공통 상위 비트와 같기 때문입니다. 하위 비트들은 범위 안에서 0과 1이 섞여 나타나므로 AND 연산 시 반드시 0이 됩니다.
C++ 구현 예제
다음 코드를 통해 더 쉽게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int i = 0;
while(m != n){
m >>= 1;
n >>= 1;
i++;
}
return m << i;
}
};
main(){
Solution ob;
cout << (ob.rangeBitwiseAnd(5,7));
}입력
5 7
출력
4
동작 과정 살펴보기
[5, 7] 범위를 예로 들면 다음과 같습니다.
- 5 = 101₂, 7 = 111₂ → 서로 다르므로 오른쪽 시프트: 2, 3 (i = 1)
- 2 = 10₂, 3 = 11₂ → 여전히 다르므로 오른쪽 시프트: 1, 1 (i = 2)
- 두 값이 1로 같아짐 → 1을 왼쪽으로 2비트 시프트하면 100₂ = 4
이 알고리즘의 시간 복잡도는 O(log n)으로, 최대 31번의 시프트만 수행하므로 매우 효율적입니다.