C++에서 n XOR (n+1) = k가 되도록 하는 수 n 찾기

문제 개요

양수 k가 주어졌을 때, n과 n+1의 XOR 연산 결과가 k와 정확히 일치하는 양수 n을 찾는 것이 목표입니다.

예를 들어 k = 7(이진수 111)이라면, 정답은 3입니다. 3은 이진수로 011이고, 3 + 1 = 4는 이진수로 100이므로 다음과 같이 계산됩니다.

011 XOR 100 = 111 (십진수 7)

해결 접근 방법

이 문제는 두 가지 경우로 나누어 분석할 수 있습니다.

경우 1: n이 짝수일 때

짝수 n의 마지막 비트는 0이고, n+1의 마지막 비트는 1입니다. 나머지 상위 비트들은 모두 동일하므로, XOR 연산 결과는 1이 됩니다.

경우 2: n이 홀수일 때

홀수 n의 마지막 비트는 1이고, n+1의 마지막 비트는 0입니다. 그러나 이 경우에는 덧셈 과정에서 발생하는 올림(carry)으로 인해 더 많은 비트가 달라지게 됩니다. 올림은 왼쪽 방향으로 전파되며, 처음으로 0 비트를 만날 때까지 계속됩니다.

따라서 n XOR (n+1)의 결과값은 2^i - 1 형태가 됩니다. 여기서 i는 n을 왼쪽부터 살폈을 때 처음 등장하는 0 비트의 위치를 의미합니다.

결론적으로, k가 2^i - 1 꼴의 숫자라면 정답 n은 k / 2가 됩니다. 만약 k가 이러한 형태가 아니라면 조건을 만족하는 n은 존재하지 않으므로 -1을 반환하면 됩니다.

구현 예제 코드

#include<iostream>
using namespace std;

int findNValue(int k) {
    // k가 1인 경우 특별 처리
    if (k == 1)
        return 2;
    // k가 2^i - 1 형태인지 확인 (k와 k+1의 AND 연산 결과가 0)
    if (((k + 1) & k) == 0)
        return k / 2;
    // 조건을 만족하는 n이 없는 경우
    return -1;
}

int main() {
    int k = 15;
    cout << "The value of n is: " << findNValue(k);
}

출력 결과

The value of n is: 7

코드 설명

위 코드에서 핵심은 ((k + 1) & k) == 0 조건입니다. 어떤 수 k가 2^i - 1 형태(즉, 이진수로 모든 비트가 1)라면, k+1은 2^i 형태가 되어 두 수의 AND 연산 결과는 반드시 0이 됩니다. 이 성질을 이용하면 k가 유효한 입력인지 빠르게 판별할 수 있습니다.

예를 들어 k = 15(이진수 1111)인 경우, 16(이진수 10000)과의 AND 연산 결과는 0이므로 유효한 입력이며, 정답은 15 / 2 = 7이 됩니다. 실제로 7(0111)과 8(1000)의 XOR은 1111 즉 15로 확인됩니다.