C++で合計が2の累乗となるペアの数を求める方法

配列が与えられたとき、要素の合計が2の累乗（1, 2, 4, 8, 16, ...）になるペアの個数を求める問題を解説します。まずは具体例を見てみましょう。

例

入力

arr = [1, 2, 3]

出力

1

この配列では、合計が2の累乗になるペアは1つだけです。該当するのは (1, 3) のペアで、合計が4になります。

アルゴリズム

解法の流れは以下のとおりです。

• 配列をランダムな数値で初期化します。
• カウント用の変数を0で初期化します。
• 二重ループを使って、配列内のすべてのペアを列挙します。
  • 各ペアの合計値を計算します。
  • ビットAND演算（&）を使って、合計が2の累乗かどうかを判定します。
  • 合計が2の累乗であれば、カウントを1増やします。
• 最終的なカウントを返します。

2の累乗の判定方法について

「(sum & (sum - 1)) == 0」という条件式がポイントです。2の累乗を二進数で表すと「1000」「10000」のように、上位1桁だけが1になります。そこから1を引くと「0111」「01111」のように下位桁がすべて1に変わるため、両者をビットANDすると必ず0になります。この性質を利用することで、割り算やループを使わずにO(1)で判定できます。

C++での実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
int get2PowersCount(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int sum = arr[i] + arr[j];
            if ((sum & (sum - 1)) == 0) {
                count++;
            }
        }
    }
    return count;
}
int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int n = 10;
    cout << get2PowersCount(arr, n) << endl;
    return 0;
}

なお、この実装ではすべてのペアを二重ループで調べるため、計算量はO(n²)となります。配列サイズが大きい場合は注意が必要です。

実行結果

上記のコードを実行すると、次の出力が得られます。

6

配列 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} の中には、合計が2の累乗になるペアが6組存在することが確認できます。