Объясните, почему x == ~ (~ x + 1) + 1 (дополнение до двух и обратно!)

Как мы все знаем, обычно отрицательные числа в памяти представляют собой два дополнительных числа вроде этого

from x to ~x + 1

и чтобы вернуться, мы не делаем очевидных вещей вроде

~([~x + 1] - 1)

но вместо этого мы делаем

~[~x + 1] + 1

может кто-нибудь объяснить, почему это всегда работает? Я думаю, что могу доказать это с помощью 1-битных, 2-битных, 3-битных чисел, а затем использовать математическую индукцию, но это не помогает мне понять, как именно это работает.

Спасибо!


binary twos-complement proof
person Solar Dia    schedule 06.11.2015    source источник
comment
По теме: Как доказать, что оператор C -x, ~ x + 1 и ~ (x-1) дает одинаковые результаты? остальные 2 тождества дополняют друг друга.   -  person Peter Cordes    schedule 06.12.2020

Ответы (2)


arrow_upward
4
arrow_downward

В любом случае это одно и то же. То есть ~x + 1 == ~(x - 1). Но пока отложим это в сторону.

f(x) = ~x + 1 - это собственное обратное. Доказательство:

~(~x + 1) + 1 =
(definition of subtraction: a - b = ~(~a + b))
x - 1 + 1 =
(you know this step)
x

Также ~x + 1 == ~(x - 1). Почему? Что ж,

~(x - 1) =
(definition of subtraction: a - b = ~(~a + b))
~(~(~x + 1)) =
(remove double negation)
~x + 1

И это (немного необычное) определение вычитания a - b = ~(~a + b)?

~(~a + b) =
(use definition of two's complement, ~x = -x - 1)
-(~a + b) - 1 =
(move the 1)
-(~a + b + 1) =
(use definition of two's complement, ~x = -x - 1)
-(-a + b) =
(you know this step)
a - b
person harold    schedule 06.11.2015
comment
Отлично. Я боролся с правильным удалением скобок. где я могу прочитать об этом определении вычитания более подробно? - person Solar Dia; 07.11.2015
comment
@SolarDia Я не знаю, но я тоже добавил доказательство для этого, но, может быть, сейчас он становится немного круглым ... - person harold; 07.11.2015
comment
Спасибо, сэр, он не круглый и выглядит очень последовательным. определение дополнения до двух - ›определение вычитания -› ~ (~ x + 1) + 1 == x не уверен, что это даже справедливо, но мне это нравится) добавлю этот комментарий, когда я получу достаточно репутации. - person Solar Dia; 09.11.2015

arrow_upward
2
arrow_downward

Это потому, что если вы увеличиваете ~ x (при отсутствии переполнения). Затем, преобразовав его обратно в x, вы увеличили относительно ~ x, но уменьшили относительно x. То же самое верно и наоборот. Предполагая, что ваша переменная x имеет определенное значение, каждый раз, когда вы увеличиваете его, относительно ~ x вы заметите, что оно уменьшается.

С точки зрения программиста, это то, что вы, по сути, стали бы свидетелями.

Let short int x = 1         (0x0001)
then ~x = 65534             (0xFFFE)
~x + 1 =  65534 + 1         (0xFFFF)
~(~x+1) = 0                 (0x0000)
~(~x+1) + 1 = 0 + 1         (0x0001)
person Iancovici    schedule 06.11.2015