C++에서 숫자를 2^x + 2^y 형태로 표현할 수 있는지 확인하는 방법

이 글에서는 주어진 숫자를 2의 거듭제곱 두 개의 합으로 표현할 수 있는지 확인하는 방법을 살펴봅니다. 즉, 수 N을 x, y > 0을 만족하는 (2^x + 2^y) 형태로 나타낼 수 있는지 검사하는 것입니다. 예를 들어 10은 2³ + 2¹로 표현할 수 있습니다.

접근 방법

풀이 아이디어는 매우 간단하며, 경우의 수는 두 가지뿐입니다.

첫 번째 경우, 수 n이 짝수라면 2^x(x > 0) 꼴의 거듭제곱 합으로 표현할 수 있습니다. 두 번째 경우, N이 홀수라면 2의 거듭제곱들의 합으로는 절대 표현할 수 없습니다. 지수 0을 사용할 수 없기 때문에, 즉 2⁰ = 1을 항에 포함할 수 없기 때문에 홀수를 만들어낼 방법이 없습니다. 실제로 모든 홀수는 이진수 표현에서 최하위 비트(LSB)가 1이라는 공통된 특징을 가집니다.

예제 코드

#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