C++で整数を2の累乗の和で表す方法 ― 指数を求めるアルゴリズムを解説

問題の概要

この問題では、整数 N が与えられます。求めるのは、N を2の累乗の和として表したときに使われる指数(べき乗の部分)を出力することです。

入出力の例

入力: 17

出力: 0, 4

説明: 17 = 2⁴ + 2⁰ = 16 + 1

解き方のアプローチ

この問題を解くには、与えられた数を 2で再帰的に割っていく 方法が有効です。この手法を使えば、任意の整数を必ず2の累乗の和として表現できます。

実は、この処理は 数を2進数に変換する手順とまったく同じ です。2進数表現で「1」が立っている桁の位置が、そのまま2の累乗の指数に対応します。たとえば 17 を2進数で表すと「10001」となり、0桁目と4桁目が1なので、答えは「0, 4」となります。

C++による実装例

以下は、この考え方を実装したサンプルプログラムです。

#include <bits/stdc++.h>
using namespace std;

void sumPower(long int x) {
    vector<long int> powers;
    // 2で割り続けて各桁(0か1)を取り出す
    while (x > 0) {
        powers.push_back(x % 2);
        x = x / 2;
    }
    // 1が立っている桁の位置(=指数)を出力
    for (int i = 0; i < powers.size(); i++) {
        if (powers[i] == 1) {
            cout << i;
            if (i != powers.size() - 1)
                cout << ", ";
        }
    }
    cout << endl;
}

int main() {
    int number = 23342;
    cout << "Powers of 2 that sum upto " << number << " are : ";
    sumPower(number);
    return 0;
}

コードのポイント

sumPower関数では、まず引数 x を2で割った余りを順に vector に格納し、2進数の各桁を求めています。その後、値が「1」になっている桁のインデックスを出力します。このインデックスこそが、2の何乗に相当するかを示す指数です。

実行結果

Powers of 2 that sum upto 23342 are : 1, 2, 3, 5, 8, 9, 11, 12, 14

この結果は、23342 = 2¹⁴ + 2¹² + 2¹¹ + 2⁹ + 2⁸ + 2⁵ + 2³ + 2² + 2¹ と表せることを意味しています。

まとめ

整数を2の累乗の和に分解する問題は、2進数変換の知識があればシンプルに解けます。計算量は数のビット長に比例する O(log N) で、非常に効率的です。ビット演算に慣れるための練習問題としても最適なので、ぜひ自分でも実装してみてください。