C++で「m個の1」と「m-1個の0」からなる最大の2進数を求める方法

このチュートリアルでは、「m個の1」と「m-1個の0」で構成される2進数の中から、与えられた数 n 未満の最大の数を求めるプログラムをC++で作成します。

まずは、問題を解決するための手順を見ていきましょう。

解法のアプローチ

• 変数 bits を 2、result を 1、i を 1 で初期化します。
• i が n 未満である間、次の処理を繰り返します。
  • i を (pow(2, bits) - 1) * pow(2, bits - 1) の計算結果で更新します。
  • 更新後の i が n 未満であれば、result をその値で上書きします。
  • bits のカウントを1つ増やします。
• 最後に result を返します。

ここで求めている数は、2進表現で「1が連続した後ろに0が1つ少ない形」で並ぶ数です。例えば、bits=2 の場合は「110」(10進数で6)、bits=3 の場合は「11100」(10進数で28)、bits=4 の場合は「1111000」(10進数で120) となり、これらは (2^bits - 1) × 2^{bits - 1} という式で表せます。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
long long getTheNumber(long long n) {
    long bits = 2;
    long long result = 1;
    long long i = 1;
    while (i < n) {
        i = (int)(pow(2, bits) - 1) * (pow(2, bits - 1));
        if (i < n) {
            result = i;
        }
        bits++;
    }
    return result;
}
int main() {
    long long n = 654;
    cout << getTheNumber(n) << endl;
    return 0;
}

出力結果

上記のコードを実行すると、次のような結果が得られます。

496

n = 654 の場合、条件を満たす最大の数は 496 です。これは2進数で「111110000」と表され、「5個の1」と「4個の0」で構成されています。

まとめ

このように、ビット演算の性質を利用した数式を使うことで、効率的に条件を満たす最大の数を求めることができます。本チュートリアルについて質問がある場合は、ぜひコメント欄でお知らせください。