2の補数による負の数の表し方の説明

同僚に2の補数に関することを質問されて改めて面白いと思ったことがあった。
２の補数は２進法においてきめられたビットの中で負の数を表せるようにする方法の１つで、たとえば、k ビットなら、 $A$ に対して、 $2^k - A$ を $-A$ とみなす方法である。 $2^k$ は k ビットでは表せないので $2^k$ は $0$ と同一視する。こうすると $A + (-A) = 0$ となるのでとても都合がいい。 $A - B = A + (-B)$ なので、引き算も足し算で表現できて、引き算用のロジックがいらない。
実際に、正の数 $A$ の2進表示（ビット列）が与えられたときにどのように $-A$ (つまり $2^k - A$ )を求めるか？
2進数では $2^k$ は $10...0$ (0がk個、kビットでは0と同一視)となり、 $2^k-1$ は $1...1$ （1がk個、kビットでは-1と同一視）となる。よって $2^k - A = 2^k -1 - A + 1$ だから、 $1...1$ (1がk個、kビットでは-1)から $A$ を引いて、 $1$ を足せばよい。ところで、 $1...1$ (1がk個)から $A$ を引くことは、丁度各ビットを反転(0→1、1→0)することに他ならない。結局 $A$ のビット列に対して、 $-A$ のビット列を求める方法の1つは、
方法１

ビット反転
1を足す

ということがわかる。簡単にするためにk=4(4ビット)とすると

aの10進表示	aの2進表示	→	-1-aの2進表示	→	-aの2進表示	-aの10進表示
1	0001	→	1110	→	1111	-1
2	0010	→	1101	→	1110	-2
3	0011	→	1100	→	1101	-3
4	0100	→	1011	→	1100	-4
5	0101	→	1010	→	1011	-5
6	0110	→	1001	→	1010	-6
7	0111	→	1000	→	1001	-7

ただし、この方法は2回走査することになるので、これは効率が悪い。
実は、 $A$ のビット列を右から1回だけ走査するだけで、 $-A$ のビット列を求めることができる。
方法２

右の桁から左の方向に桁を見ていきながら下に別のビット列を書いていく。右から0が続く間は、0を下に書き写す。1がはじめて現れたところで、その桁の下に1を書いて、次の桁からは、上の数字の反転(0→1、1→0)を書く。

すると、 $A$ のビット列の下に $-A$ のビット列が得られる！
以下で確認できる。

1	2	3	4	5	6	7
0001	0010	0011	0100	0101	0110	0111
1111	1110	1101	1100	1011	1010	1001

では、なぜそうなるのか？同僚が疑問に思ったのもここである。一見不思議に見える。
しかし、これは実は最初の方法

ビット反転
1を足す

を一度にやっただけなのである。
まず、一番右の桁だけ考える。

0ならば、ビット反転で1、1足して、その桁だけ考えれば0になる。結局、0→0。
1ならば、ビット反転で0、1足して、その桁だけ考えれば1になる。結局、1→1。

ただし、0だった場合は繰上りが発生して、左の桁に1足されることになる。左の桁について、反転して、1を足すという操作が起こることになる。右側の桁を忘れてしまえばこの桁が一番右の桁になるので、先ほどの桁と同様になる。つまり、今見ている桁が0であるうちは左の桁にも同じこと（反転と1足すこと）が起きる。今見ている桁が1になったとき、繰り上がりが発生しないので、左の桁に1を足すは起こらない。つまり、それより左の桁は最初の方法の反転だけ実行したものになる。