C++で整数Nが2^x + 2^yの形で表現できるかを判定する方法

この記事では、与えられた整数Nが、2つの0でない2の冪の和――すなわち 2^x + 2^y（x, y > 0）――の形で表現できるかどうかを判定する方法を解説します。例えば10は 2³ + 2¹ = 8 + 2 と表せるため、条件を満たします。

考え方：数の偶奇に着目する

判定のアプローチは非常にシンプルで、次の2つのケースに分けて考えます。

• Nが偶数の場合：2の冪の和として表現できると判定します。偶数は 2^x（x > 0）の形で扱うことができます。
• Nが奇数の場合：表現できません。x, y > 0 の制約下では 2^x も 2^y も必ず偶数になるため、その和も必然的に偶数になります。これは、奇数の2進表現の最下位ビット（LSB）が必ず1になっていることからも確認できます。

判定手順

1. 入力された数 n を受け取ります。
2. 「n & 1」（ビットごとのAND）が0であれば偶数なので、true を返します。
3. それ以外（奇数）の場合は false を返します。

C++での実装例

#include <iostream>
using namespace std;

// n が 2^x + 2^y（x, y > 0）の形で表せるかを判定する
bool isSumofTwosPower(int n) {
    if ((n & 1) == 0) {
        return true;   // 偶数なら表現可能
    } else {
        return false; // 奇数は表現不可
    }
}

int main() {
    int num = 86;
    if (isSumofTwosPower(num)) {
        cout << "2の冪の和として表現できます";
    } else {
        cout << "2の冪の和として表現できません";
    }
}

実行結果

2の冪の和として表現できます

補足

ここで紹介した判定は「偶数なら表現可能」というシンプルなルールに基づいています。もし「ちょうど2つの2の冪の和」と厳密に判定したい場合は、2進表現におけるセットビット（1になっているビット）の数を数える __builtin_popcount(n) を活用するなど、目的に応じた方法を使い分けるとよいでしょう。