C++로 두 숫자의 가장 오른쪽 다른 비트 위치 찾기

이 문제에서는 두 개의 숫자 N과 M이 주어지며, 두 수의 이진수 표현에서 서로 다른 비트 중 가장 오른쪽에 있는 비트의 위치(인덱스)를 찾아야 합니다.

문제 이해하기

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

입력 − N = 12, M = 10

출력 − 2

설명 − (12)₂ = 1100 이고 (10)₂ = 1010 입니다. 오른쪽에서 두 번째 비트가 서로 다른 비트입니다.

해결 접근 방법

이 문제를 해결하려면 두 숫자에서 서로 다른 모든 비트를 찾아야 합니다. 가장 효율적인 방법은 N과 M에 대해 XOR 연산을 수행하는 것입니다. XOR 연산 결과에서 값이 1인 비트는 두 숫자가 서로 다른 비트임을 의미합니다. 그다음, XOR 결과값에서 가장 오른쪽에 있는 1비트(설정된 비트)의 위치를 찾으면 됩니다.

말로만 들으면 다소 복잡하게 느껴질 수 있으니, 예시를 통해 이 방법을 직접 확인해 보겠습니다.

N = 12 , M = 10
N^M = 0110

XOR 결과 0110에서 가장 오른쪽에 설정된 비트는 인덱스 2에 위치합니다.

가장 오른쪽 설정 비트 찾기

XOR 결과에서 가장 오른쪽 1비트는 N & -N 연산을 통해 구할 수 있습니다. 이 연산은 N에서 가장 오른쪽에 설정된 비트만 남기고 나머지 비트는 모두 0으로 만듭니다. 여기에 log2를 적용한 뒤 1을 더하면 해당 비트의 위치(1부터 시작하는 인덱스)를 얻을 수 있습니다.

구현 예제

위에서 설명한 해결 방법을 구현한 프로그램입니다.

#include <iostream>
#include <math.h>
using namespace std;

int rightSetBit(int N) {
    int bitIndex = log2(N & -N) + 1;
    return bitIndex;
}

void rightDiffBit(int m, int n) {
    int diffBit = rightSetBit(m ^ n);
    cout << diffBit;
}

int main() {
    int N = 12, M = 10;
    cout << "숫자 " << N << " 과 " << M << " 의 가장 오른쪽 다른 비트 위치는 ";
    rightDiffBit(N, M);
    return 0;
}

출력

숫자 12 과 10 의 가장 오른쪽 다른 비트 위치는 2

복잡도 분석

시간 복잡도: O(1) — XOR 연산과 log2 계산은 상수 시간 안에 수행됩니다.
공간 복잡도: O(1) — 추가적인 메모리 공간을 사용하지 않습니다.