C++에서 숫자가 2의 거듭제곱 두 개의 합으로 표현 가능한지 확인하는 방법

이번 글에서는 하나의 자연수를 2의 0이 아닌 거듭제곱 두 개의 합으로 나타낼 수 있는지 확인하는 방법을 살펴보겠습니다. 다시 말해, 주어진 숫자 N을 2^x + 2^y(단, x, y > 0) 형태로 표현할 수 있는지 검사하는 문제입니다. 예를 들어 숫자 10은 2³ + 2¹, 즉 8 + 2로 표현할 수 있으므로 조건을 만족합니다.

접근 방법

풀이 아이디어는 매우 단순하며, 크게 두 가지 경우로 나누어 생각할 수 있습니다.

• N이 짝수인 경우: 지수가 1 이상인 2의 거듭제곱들은 모두 짝수이므로, 그 합 역시 항상 짝수가 됩니다. 따라서 짝수라면 두 거듭제곱의 합으로 표현 가능하다고 판단할 수 있습니다.
• N이 홀수인 경우: 지수 0, 즉 2⁰ = 1은 사용할 수 없기 때문에 홀수는 절대 두 거듭제곱의 합이 될 수 없습니다. 실제로 모든 홀수는 이진수 표현에서 최하위 비트(LSB)가 1이라는 특징이 있습니다.

결국 숫자의 홀짝 여부만 판별하면 되며, 이는 비트 AND 연산(n & 1)을 이용하면 아주 빠르게 확인할 수 있습니다. 참고로 표현 가능한 가장 작은 수는 2¹ + 2¹ = 4이므로, 실전 구현에서는 n ≥ 4 조건을 함께 검사하면 더욱 안전합니다.

C++ 구현 예제

#include <iostream>
using namespace std;
bool isSumofTwosPower(int n) {
    if((n & 1) == 0){
        return true;
    } else {
        return false;
    }
}
int main() {
    int num = 86;
    if(isSumofTwosPower(num)){
        cout << "Can be represented";
    } else {
        cout << "Cannot be represented";
    }
}

실행 결과

Can be represented

예제에서 사용한 숫자 86은 짝수이므로 "Can be represented(표현할 수 있음)"라는 결과가 출력됩니다. 반면 87처럼 홀수를 입력하면 최하위 비트가 1이므로 "Cannot be represented(표현할 수 없음)"가 출력됩니다. 이처럼 비트 연산 한 번만으로 O(1) 시간에 문제를 해결할 수 있다는 점이 이 방법의 가장 큰 장점입니다.