Pythonで2つの数値の指定範囲のビットが互いに補完関係にあるか確認する方法

2つの数値 x と y、および範囲（left, right）が与えられたとき、両方の数値の left 桁目から right 桁目までのビットが互いに補完関係（反転）になっているかどうかを判定する必要があります。なお、ビット位置は右から左へ数え、最下位ビット（LSB）が1桁目として扱われます。

例えば、入力が x = 41、y = 54、left = 2、right = 5 の場合、出力は True になります。41 と 54 の2進表現はそれぞれ 101001 と 110110 であり、2桁目から5桁目までのビットは「1001」と「0110」で、互いに補完関係にあるためです。

解決のアプローチ

この問題は、XOR（排他的論理和）演算の性質を利用することで効率的に解けます。XORでは、対応するビットが異なる場合に1が出力されるため、x と y の指定範囲のビットが完全に補完関係であれば、x XOR y のその範囲のビットはすべて1になるはずです。

具体的には、以下の手順で判定を行います。

• temp := x XOR y を計算する
• temp の left 桁目から right 桁目までのすべてのビットが1であれば True を返し、そうでなければ False を返す

実装例

def are_all_setbits_in_range(n, left, right):
    # left桁目からright桁目までが1となるビットマスクを作成
    val = ((1 << right) - 1) ^ ((1 << (left - 1)) - 1)
    new_value = n & val
    if val == new_value:
        return True
    return False

def solve(x, y, left, right):
    temp = x ^ y
    return are_all_setbits_in_range(temp, left, right)

x = 41
y = 54
left = 2
right = 5
print(solve(x, y, left, right))

コードの解説

• ビットマスクの作成：((1 << right) - 1) で下位 right 桁がすべて1の値を作り、((1 << (left - 1)) - 1) で下位 left-1 桁がすべて1の値を作ります。両者をXORすることで、left 桁目から right 桁目だけが1のマスクが得られます。
• ビットの抽出：n & val により、対象範囲のビットのみを取り出します。
• 判定：抽出結果がマスク全体と一致すれば、範囲内のすべてのビットが1であること、つまり元の2つの数値のビットが補完関係にあることを意味します。

入力

41, 54, 2, 5

出力

True

この手法の計算量は O(1) であり、ビット演算のみで構成されているため非常に高速です。大きな数値を扱う場合でも、範囲内のビットを1つずつ比較する方法よりもはるかに効率的に判定できます。