Pythonで一方の数値がもう一方の1の補数かどうかを判定する方法

1の補数とは

2つの数値 x と y が与えられたとき、一方がもう一方の「1の補数」になっているかどうかを判定する問題を考えてみましょう。1の補数とは、2進数表現におけるすべてのビットを反転させる(0を1に、1を0にする)操作のことです。

例えば、x = 9、y = 6 の場合、2進数表現はそれぞれ x = 1001、y = 0110 となり、互いに補数の関係にあるため、出力は True になります。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• z = x XOR y を計算する
• z のすべてのビットが1になっていれば True、そうでなければ False を返す

x と y が互いの補数であれば、対応する各ビットは必ず異なる値になるため、XOR 演算の結果はすべてのビットが1の数値になります。したがって、「z の全ビットがセットされているか」を確認するだけで判定できるのです。

実装例

以下のコードで実際の実装を見てみましょう。

def all_one(n):
    if n == 0:
        return False
    if ((n + 1) & n) == 0:
        return True
    return False

def solve(x, y):
    return all_one(x ^ y)

x = 9
y = 6
print(solve(x, y))

all_one 関数の仕組み

ある数 n の全ビットが1であるかどうかは、(n + 1) & n == 0 という条件で判定できます。例えば n = 7(2進数で 111)の場合、n + 1 = 8(2進数で 1000)となり、両者の AND 演算結果は 0 になります。これは、全ビットが1の数に1を加えると桁上がりによって既存のビットがすべて0になり、新たな上位ビットだけが1になるためです。

入力と出力

入力:

9, 6

出力:

True

まとめ

XOR 演算とビット判定を組み合わせることで、2つの数値が互いの1の補数かどうかを短時間で判定できます。ビット演算を活用したシンプルかつ効率的なテクニックなので、競技プログラミングや実務でもぜひ覚えておきましょう。