math - 2 の補数の証明

Question

長さ n のすべてのシーケンスについて、任意の 0 の文字列の 2 の補数が常に 0 になることを帰納法によって証明することは可能ですか?

値式を使用してこれを実行しようとしています。

値 = -a_n-1 x 2^(n-1) + summation{i=0 to n} (a_i x 2^i)、n = 文字列のビット数

Answer 1

たとえば、 の 2 の補数が であることを証明したいの1111 1111です0000 0000か? もしそうなら、それは嘘なので証明できません。の 2 の補数は1111 1111です0000 0001。

    1111 1111
->  0000 0000 <- one's complement
->  0000 0001 <- add 1

あなたの編集への応答: 承知しました。しかし誘導は必要ありません。のすべてのビットを反転し0_nて 1 の補数を取得する1_nと、1すべてのビットが反転して 0 に戻ります (1 + 1 = 10キャリー ビットは、ドロップした場所まで浸透します)。QED。

Answer 2

1) X の 2 の補数の定義: X のビットを反転して 1 を合計する

2) 1 ビットの 2 つの変数のバイナリ和 (http://www.play-hookey.com/digital/adder.html) (b1 は最初の変数、b2 は 2 番目の変数です。b1:X は変数のビット X を表します) )

r1 = b1:1 XOR b2:1
carry = b1:1 AND b2:1

2.1) 両方のビットが 1 の場合 b1:1 と b2:1

r1 = 0  (always)
carry = 1 (always)

3) 2 ビットの 2 つの変数のバイナリ和

r1 = b1:1 XOR b2:1 
carry1 = b1:1 AND b2:1

r2 = (b1:2 XOR b2:2) XOR carry:1
carry2 = (b1:2 AND b2:2) OR (b1:2 AND carry:1) OR (b2:2 AND carry:1)

3.1) 2.1 から

carry2 = (b1:2 AND b2:2) OR (b1:2 AND 1) OR (b2:2 AND 1)
carry2 = b1:2 OR b2:2

4) ゼロすべてゼロの数字であること。すべてのビットを反転すると、すべて 1 の数値が生成されます: Ones

5) Bit0 XOR Anything = Anything (XOR の真理値表)

6) 数ゼロに (1) を適用する

6.1) フリップ

 Flipping Zero = Ones

6.2) 合計 1

 result = Ones + N_One (N_One = 00...001)
 result:1 = 0 (from 2.1)
 carry:1 = 1 (from 2.1)

6.3) N_One:1 を除く N_One からのすべてのビットがゼロであるため。

 result:n = (Ones:n XOR N_One:n) XOR carry:(n-1) (from 3)
 result:n = (Ones:n XOR 0) XOR carry:(n-1) (definition of N_One 6.2)
 result:n = Ones:n XOR carry:(n-1)

6.4) 3.1 から

carry:n = Ones:n OR N_One:n -> if carry:n-1 is 1
carry:n = 1 OR 0            -> if carry:n-1 is 1
carry:n = 1                 -> if carry:n-1 is 1

最初のキャリー (carry:1) が 6.1 から 1 として定義されるため、すべてのキャリーが 1 として定義されます。

7) 6.3 および 6.4 から

 result:n = Ones:n XOR carry:(n-1)
 result:n = 1 XOR 1
 result:n = 0

n の任意の値について、(~n+1) が常に 0 であることを証明します (固定ビットフィールド サイズのマシンの最後のキャリーは常に無視されます)。

QED

Answer 3

111..111の 2 の補数はちょうど1ではありませんか (つまり、111..111 は -1 を表します)。