C++でビットを削除して2進数が64で割り切れるか判定するプログラム

はじめに

このチュートリアルでは、与えられた2進数からいくつかのビットを削除することで64の倍数にできるかどうかを判定するC++プログラムを作成します。

2進数が1つ与えられ、任意のビットを取り除くことができます。ビットを削除した後の数が64で割り切れる場合はYesを、そうでない場合はNoを出力します。

アルゴリズムの考え方

64は2の6乗（2⁶）です。したがって、2進表現において64の倍数は必ず下位6桁以上が0になっています。逆に言えば、「ある1のビットよりも下位に0が6個以上存在する」ならば、その1と0だけを残して残りのビットをすべて削除することで、64で割り切れる数を作ることができます。

この性質を利用すると、以下のようなシンプルな手順で問題を解けます。

• 2進数を文字列形式で初期化します。

• 与えられた2進数を下位の桁から順に走査します。

• 0の個数をカウントしていきます。

• 走査中に1のビットを見つけ、その時点でカウント済みの0が6個以上であれば、その数は64で割り切れると判定できます。

• 最後に、与えられた2進数が64で割り切れるかどうかの結果を出力します。

実装例

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

#include <bits/stdc++.h>
using namespace std;
bool isBinaryStringDivisibleBy64(string binary_number, int n) {
    int zeroes_count = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (binary_number[i] == '0') {
            zeroes_count++;
        }
        if (zeroes_count >= 6 && binary_number[i] == '1') {
            return true;
        }
    }
    return false;
}
int main() {
    string binary_string = "100100100100100";
    if (isBinaryStringDivisibleBy64(binary_string, 15)) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

出力

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

Yes

まとめ

このアルゴリズムは文字列を一度走査するだけでよいため、時間計算量はO(n)と非常に効率的です。64が2の累乗であるという性質を活かすことで、実際にビットを削除する操作を行わずに判定できる点がポイントです。

本チュートリアルについてご不明な点がありましたら、コメント欄でお気軽にお知らせください。