C++で数値が2つの非ゼロの2の累乗の和として表せるか判定する方法

本記事では、ある整数Nを「2つの非ゼロの2の累乗の和」、すなわち 2^x + 2^y（x, y > 0）という形で表すことができるかどうかを判定する方法を解説します。例えば 10 は 2³ + 2¹ と表せるため、条件を満たします。

考え方：偶奇に着目する

2の累乗（2¹, 2², 2³, …）はすべて偶数なので、その和も必ず偶数になります。この性質から、次のように判定できます。

• Nが奇数の場合： 表現することはできません。奇数の2進表現は最下位ビット（LSB）が必ず1になるためです。
• Nが偶数の場合： 表現できる可能性があります。最下位ビットが0かどうかをビット演算で調べるだけで簡単にチェックできます。

偶数でも表現できないケースに注意

より正確に言うと、「2つの累乗の和」は2進表現で見ると「1のビットが1個または2個」の数に対応します。同じ累乗を2回足せば桁上がりして1ビットになり、異なる累乗の和なら2ビットになるためです。そのため、次のような数は偶数であっても表現できません。

• 2進表現で1のビットが3個以上ある数（例：14 = 8 + 4 + 2）
• N = 2（和の最小値は 2 + 2 = 4 であるため）

C++での実装例

まずは、最下位ビットの判定のみを行うシンプルな実装です。

#include <iostream>
using namespace std;

// Nが2つの非ゼロの2の累乗の和で表せるかを判定する
bool isSumOfTwosPower(int n) {
    if ((n & 1) == 0) {
        return true;   // 偶数なら表現可能
    } else {
        return false;  // 奇数なら表現不可能
    }
}

int main() {
    int num = 10;
    if (isSumOfTwosPower(num)) {
        cout << "Can be represented";
    } else {
        cout << "Cannot be represented";
    }
}

出力

Can be represented

補足：popcountによる厳密な判定

上記の実装は「偶数なら表現できる」という簡易的な判定です。14 のような例外を正しく扱いたい場合は、2進表現に含まれる1のビットの個数（ポピュレーションカウント）を使うと便利です。GCC / Clang では __builtin_popcount 関数を利用できます。

#include <iostream>
using namespace std;

bool isSumOfTwosPower(int n) {
    // 4以上 かつ 1のビットが2個以下なら表現可能
    return n >= 4 && __builtin_popcount(n) <= 2;
}

int main() {
    int nums[] = {10, 14, 86};
    for (int num : nums) {
        cout << num << ": ";
        if (isSumOfTwosPower(num))
            cout << "Can be represented" << endl;
        else
            cout << "Cannot be represented" << endl;
    }
}

出力

10: Can be represented
14: Cannot be represented
86: Cannot be represented

まとめ

• 2の累乗はすべて偶数なので、その和も偶数になる。したがって奇数は必ず表現不可能。
• 偶数は原則として表現可能だが、1のビットが3個以上の数（例：14）や N = 2 は例外。
• 厳密に判定したい場合は「N ≥ 4 かつ ビットカウント ≤ 2」という条件を使うとよい。