이 문제에서는 두 개의 숫자 M과 N이 주어지며, 두 숫자가 공통으로 가지는 비트 중 가장 오른쪽에 있는 비트의 위치(인덱스)를 출력하는 것이 목표입니다.
문제 예시
- 입력: N = 4, M = 7
- 출력: 3
- 설명: (4)₂ = 100, (7)₂ = 111 입니다. 오른쪽부터 비교했을 때 처음으로 일치하는 비트는 3번째 자리에 있습니다.
해결 접근 방법
이 문제를 해결하려면 두 숫자의 모든 공통 비트를 찾아야 합니다. 핵심 아이디어는 다음과 같습니다.
- XOR 연산: M ^ N은 두 숫자에서 서로 다른 비트만 1로 표시합니다.
- 비트 반전(NOT): ~(M ^ N)을 계산하면 두 숫자가 같은 값을 가지는 비트만 1로 표시됩니다.
- 가장 오른쪽 설정 비트 찾기: 반전된 값에서 가장 오른쪽에 있는 1비트의 위치를 구하면, 그것이 곧 우리가 찾는 가장 오른쪽 공통 비트의 위치입니다.
말로 설명하면 다소 복잡하게 느껴질 수 있으니, 예제를 통해 단계별로 확인해 보겠습니다.
N = 4 , M = 7 ~(N^M) = 100.
여기서 가장 오른쪽에 설정된(set) 비트는 3번째 인덱스에 위치합니다.
참고로 x & -x 연산은 x의 가장 오른쪽 설정 비트만 남기고 나머지 비트를 모두 0으로 만드는 널리 알려진 비트 조작 기법입니다. 여기에 log₂를 취하고 1을 더하면 오른쪽부터 셌을 때의 비트 위치를 손쉽게 얻을 수 있습니다.
구현 예제
위에서 설명한 해결 방법을 구현한 프로그램입니다.
#include <iostream>
#include <math.h>
using namespace std;
int rightSetBit(int N) {
int bitIndex = log2(N & -N) + 1;
return bitIndex;
}
void rightSameBit(int m, int n) {
int diffBit = rightSetBit(~(m^n));
cout << diffBit;
}
int main() {
int N = 4, M = 7;
cout << "Position of first right same bit of the number " << N << " & " << M << " is ";
rightSameBit(N, M);
return 0;
}
출력 결과
Position of first right same bit of the number 4 & 7 is 3
코드 설명
rightSetBit()함수:N & -N으로 가장 오른쪽 설정 비트만 추출한 뒤, log₂를 이용해 위치를 계산하고 1을 더해 반환합니다.rightSameBit()함수:~(m^n)으로 두 숫자의 공통 비트만 추출한 후, 이를rightSetBit()에 전달하여 결과를 출력합니다.main()함수: 예제 입력 N = 4, M = 7을 사용해 최종 결과를 화면에 출력합니다.
이 방식은 XOR, NOT, AND 같은 기본적인 비트 연산만 사용하므로 시간 복잡도는 사실상 O(1)로 매우 효율적입니다.