Два Комплимента Quick Way

Question

Способ найти дополнение двоичного числа двоичного числа:

1. Пусть x ̄ = логическое дополнение x.Логическое дополнение (также называемое дополнением к одному) формируется путем переворачивания всех битов числа, изменения всех 1 битов на 0 и наоборот.
2. Пусть X = x ̄ + 1. Если этоПри дополнительном переполнении бит переполнения сбрасывается.По определению дополнения к двум, X ≡ −x.

Я видел быстрый способ, который:

например.

B = 00010110 D = 22 * ​​1016 *

Отразить все после первого "1", считая с левой стороны.

-B = 11101010 -D = -22

Я не мог понять доказательство этого пути.

Answer 1

Если вы возьмете определение -x = ~x + 1, то если мы представим x в виде строки a10 ^k (строка a, за которой следует 1, за которым следует k нулей), то:

-(a10^k) =
// by definition
~(a10^k) + 1 =
// complement distributes over concatenation
~a01^k + 1 =
// carry through the 1s and set the 0
~a10^k

Конечный результат, ~a10^k, означает «дополнить левую сторону, пока (не включая) самую правую 1».

Это доказательство не выполнялось для x = 0, так какон не может быть записан в форме a10 ^k , эквивалентность по-прежнему верна: нет части, которую можно дополнить, поскольку нет самой правой 1, поэтому результат снова равен нулю, что является правильным.