C++에서 이전 숫자가 1의 보수와 같은지 확인하는 방법

문제 소개

이 문제에서는 하나의 정수 n이 주어집니다. 우리가 해야 할 일은 n보다 1 작은 수, 즉 바로 앞의 숫자가 n의 1의 보수(1's complement)와 동일한지 확인하는 것입니다.

몇 가지 예시를 통해 문제를 이해해 보겠습니다.

입력: 12
출력: No
설명: (12)10 = (1100)2
바로 앞의 숫자 11 = (1011)2
12의 1의 보수 = (0011)2

입력: 4
출력: Yes
설명: 4 = (100)2
바로 앞의 숫자 3 = (011)2
4의 1의 보수 = (011)2

단순한 접근 방법

가장 직관적인 방법은 n-1을 직접 구하고, n의 1의 보수를 계산한 뒤 두 값을 하나씩 비교하는 것입니다.

이 방법은 구현이 간단하지만 각 비트를 개별적으로 처리해야 하므로 시간과 공간을 추가로 소모하게 됩니다. 시간 복잡도는 O(n)입니다.

효율적인 해결 방법

더 효율적인 접근법은 문제의 수학적 성질을 활용하는 것입니다. 분석해 보면 2의 거듭제곱에 해당하는 숫자만 이 조건을 만족합니다. 즉, n이 2의 거듭제곱일 때만 바로 앞의 숫자가 n의 1의 보수와 같아집니다.

그 이유는 다음과 같습니다. 2의 거듭제곱인 수는 이진법으로 최상위 비트 하나만 1이고 나머지는 모두 0입니다(예: 4 = 100). 이때 n-1은 그 아래 자릿수가 모두 1로 채워집니다(예: 3 = 011). 이 값은 n의 1의 보수와 정확히 일치합니다.

따라서 비트 연산 n & (n - 1)의 결과가 0인지만 확인하면 됩니다. 이 조건은 n이 2의 거듭제곱인지 판별하는 널리 알려진 기법으로, 시간 복잡도는 O(1)입니다.

구현 코드

#include <iostream>
using namespace std;
bool sameBits(unsigned long int n){
    if ((n & (n - 1)) == 0)
        return true;
    return false;
}
int main(){
    unsigned long int n = 64;
    if(sameBits(n))
        cout<<"Both are the same";
    else
        cout<<"Both aren't the same";
    return 0;
}

실행 결과

Both are the same

위 코드에서 n = 64는 2의 거듭제곱(2⁶)입니다. 64의 이진 표현은 1000000₂이며, 바로 앞의 숫자 63은 111111₂로 64의 1의 보수와 일치하므로 "Both are the same"이 출력됩니다.