Pythonで10進数整数の2進補数（ビット補完）を求める方法

この記事では、10進数で与えられた整数に対して、その2進表現における補数（ビット反転）を求め、再び10進数に変換して返す方法を解説します。

例として、数値が 20 の場合を考えてみましょう。20の2進表現は 10100 です。これをビットごとに反転すると 01011 となり、これを10進数に戻すと 11 になります。これが求める答えです。

解法のアプローチ

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

• s を数値 n の2進表現の文字列とします（Pythonの bin() 関数を使うと「0b」プレフィックス付きの文字列が得られます）。
• sum = 0、num = 1 で初期化します。
• 文字列 s を末尾から先頭に向かって1文字ずつ処理します。
  • 現在の文字が 'b' であれば、「0b」プレフィックスに到達したことを意味するので、そこで sum を返して終了します。
  • 現在の文字が '0' であれば、元の数ではその桁が1だったことを意味するため、sum += num として値を加算します。
  • 1文字処理するごとに num *= 2 として桁の重みを2倍にしていきます。

つまり、元の2進表現で「0」だった桁だけを1として足し合わせることで、補数の値を効率的に計算できます。

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution(object):
    def bitwiseComplement(self, N):
        s = str(bin(N))
        sum = 0
        num = 1
        for i in s[::-1]:
            if i == "b":
                return sum
            elif i == "0":
                sum += num
            num *= 2

ob1 = Solution()
print(ob1.bitwiseComplement(20))

入力

20

出力

11

コードのポイント

• bin(N) は数値を「0b10100」のような形式の文字列に変換します。スライス s[::-1] を使うことで、文字列を逆順に走査しています。
• 逆順に走査することで、下位ビットから順に処理でき、num を2倍ずつ増やしながら各桁の重みを正しく反映できます。
• 計算量は2進表現の桁数に比例し、O(log N) で非常に効率的です。