Pythonで指定範囲内のすべての数値のビットごとのAND（論理積）を求めるプログラム

2つの整数 start と end が与えられたとき、閉区間 [start, end]（両端を含む）に含まれるすべての数値のビットごとのAND（論理積）を求めることを考えます。

例として、start = 8、end = 12 の場合を見てみましょう。8 は2進数で「1000」、12 は「1100」と表されます。したがって、
1000 AND 1001 AND 1010 AND 1011 AND 1100
を計算すると「1000」、すなわち答えは 8 になります。

解法の手順

この問題は、次の手順で解くことができます。

• n := end − start + 1（範囲に含まれる数値の個数）とします。
• x := 0（結果を格納する変数）と初期化します。
• b を 31 から 0 まで 1 ずつ減らしながら繰り返します。
  • 2^b < n となる場合は、ループから抜け出します。
  • 2^b AND start AND end が 0 以外の場合は、x := x + 2^b とします。
• 最後に x を返します。

このアルゴリズムのポイントは、連続する整数の範囲において、あるビット位置が範囲の長さ以上の幅を持つ場合にのみ、そのビットがすべての数で共通して立つという性質を利用している点です。上位ビットから順に確認することで、範囲内の全数値に共通して立っているビットだけを結果に加算していきます。

実装例

理解を深めるために、以下のPython実装を見てみましょう。

def solve(start, end):
    n = end - start + 1
    x = 0
    for b in range(31, -1, -1):
        if (1 << b) < n:
            break
        if (1 << b) & start & end:
            x += 1 << b
    return x

start = 8
end = 12
print(solve(start, end))

入力

8, 12

出力

8