Pythonで数値の2進表現における0と1の連続ブロックの長さが等しいかどうかを判定する

問題の概要

ある整数 num が与えられたとき、その2進表現を「連続した同じビットの並び(ブロック)」に分割し、0 のブロックと 1 のブロックの長さがすべて等しいかどうかを判定します。ただし、「0」そのものや、すべてのビットが「1」で構成される数値は、ブロック数の比較対象とはみなされません。

例として、num = 455 の場合を考えてみましょう。455 の2進表現は 111000111 であり、「111」「000」「111」という3つのブロックに分けられます。各ブロックの長さはすべて 3 で等しいため、出力は True になります。

解法の手順

この問題は、以下の手順に従って解くことができます。

• bin_form := num の2進表現(文字列)
• one_count := 各ブロックの長さを記録するための空の集合(set)
• count := 1(現在調べているブロックの長さ)
• i を 0 から bin_form のビット数 - 2 まで繰り返す
  • bin_form[i] と bin_form[i + 1] が同じ場合は、count を 1 増やす
  • 異なる場合は、count を one_count に追加し、count を 1 にリセットする
• one_count のサイズが 1 であれば True を返す
• それ以外の場合は False を返す

それでは、実際の実装を見ながら理解を深めていきましょう。

サンプルコード

def solve(num):
    bin_form = bin(num).replace("0b", "")
    one_count = set()
    count = 1

    for i in range(len(bin_form)-1):
        if bin_form[i] == bin_form[i + 1]:
            count += 1
        else:
            one_count.add(count)
            count = 1

    if len(one_count) == 1:
        return True
    return False

num = 455
print(solve(num))

入力

455

出力

True

コードの解説

まず bin(num) 関数で数値を2進表現の文字列に変換し、replace() メソッドで不要な接頭辞 "0b" を取り除きます。続いて、文字列を先頭から順に走査しながら隣接するビット同士を比較します。同じビットが続いている間は count を加算し、ビットが切り替わったタイミングで、それまでのブロックの長さを集合 one_count に記録していきます。

最終的に one_count に含まれる長さの種類が 1 つだけであれば、検出されたすべてのブロックが同じ長さであることを意味するため、True を返します。

なお、上記の実装ではループ終了時に数えていた最後のブロックの長さは集合に追加されません。より厳密に判定したい場合は、ループ処理の直後に one_count.add(count) を追加しておくと、末尾のブロックも確実に検証できるようになり、より堅牢な実装になります。