C++で2進数から1ビットを削除して最大値を求める方法

問題の概要

本記事では、与えられた2進数から1ビットを削除し、残りのビットで表される数が他のすべての選択肢の中で最大になるようにする問題を解説します。

入力 : N = 1011
出力: 111
説明: 1ビットを削除する必要があります。「0」のビットを削除すると、いずれかの「1」のビットを削除した場合よりも大きな数になります。111 > 101, 011

入力: 111
出力: 11
説明: すべてのビットが「1」なので、どのビットを削除しても結果は同じになります。

解決アプローチ

全探索（ブルートフォース）法

最も単純な方法は、各ビットを1つずつ削除してみて、それぞれの結果を比較し、最大の結果を得るという全探索です。この方法でも確かに最大値は求まりますが、計算量が多くなります。

しかし、この問題には効率的なアプローチが存在します。それは「最も影響の少ないビット」を削除するという考え方です。

効率的なアプローチ

効率的なアプローチでは、結果の数値への影響が最小となるビットを削除します。手順は以下の通りです。

• まず、右側からビットを走査します。

• 「0」を探し、最初に見つかった時点でそれを削除します。

• 「0」が見つからなかった場合（すべてのビットが「1」の場合）は、任意のビットを削除します。

実装例

効率的なアプローチのC++コード

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str = "1011";
    bool flag = false;
    int n = str.length();
    // 結果を格納する新しい配列を初期化
    char res[n - 1];
    int j = 0;
    // 2進数を先頭から走査
    for (int i = 0; j < n - 1; i++) {
        // 「0」が見つかった場合はスキップ
        if (str[i] == '0' && flag == false) {
            flag = true;
            continue;
        }
        else
            res[j++] = str[i];
    }
    // 結果の文字列を出力
    cout << "Maximum number: " << res;
    return 0;
}

実行結果

Maximum number: 111

コードの解説

• フラグ変数（flag）を使用することで、削除される「0」は1つだけであることを保証しています。

• 結果の数値を格納するために、文字型配列resを初期化しています。

• ループはn-1回まで実行されます。これは、元の数より1つ少ない要素を格納する必要があるためです。

まとめ

本チュートリアルでは、2進数から1ビットを削除した後に得られる最大の数を求める問題について解説しました。全探索と効率的なアプローチの2つの解法を取り上げ、その違いを確認しました。

また、C++での実装コードを紹介しましたが、同じロジックはC、Java、Pythonなど他の言語でも同様に実装できます。本チュートリアルが皆さんの学習に役立てば幸いです。