Как доказать, что оператор C -x, ~ x + 1 и ~ (x-1) дают те же результаты?

Ответ 1

Подумайте, что вы получаете, когда добавляете число в его побитовое дополнение. Побитовое дополнение n-битового целого x имеет 1, всюду x имеет 0, и наоборот. Поэтому ясно, что:

x + ~ x = 0b11... 11 (n-разрядное значение для всех)

Независимо от количества бит в x. Кроме того, обратите внимание, что добавление одного к n-разрядному числу, заполненному всеми, приведет к обнулению. Таким образом, мы видим:

x + ~ x + 1 = 0b11... 11 + 1 = 0 и ~ x + 1 = -x.

Аналогично, обратите внимание (x - 1) + ~ (x - 1) = 0b11... 11. Тогда (x - 1) + ~ (x - 1) + 1 = 0 и ~ (x - 1) = -x.

Ответ 2

Я не уверен, что вы можете доказать это из какой-либо полезной аксиомы, кроме довольно тривиальной редукции, к тому, что мы определили отрицательные числа в современных целочисленных ALU, чтобы быть в двух дополнениях.

Компьютеры не обязательно должны быть реализованы с использованием двухкомпонентного бинарного оборудования, это просто, что есть различные привлекательные свойства, и почти все построено таким образом в наши дни. (Но не с плавающей точкой! Это одно дополнение!)

Итак, мы создаем машину, которая, как представляется, представляет отрицательные числа в 2 дополнениях. Выражения, которые показывают отрицательные числа, которые должны быть представлены в двух дополнениях, точны, но только потому, что мы определили их таким образом. Это аксиоматическая основа для отрицательных целых чисел в современных машинах.

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

Может быть, именно поэтому я на самом деле не парень теории.: -)

Ответ 3

~ x + 1 эквивалентно 2 дополнениям + 1 (т.е. отрицательному числу), представления -x, ~ (x-1) также представляют одно и то же (рассмотрим случай, когда последний бит равен 1, ~ (x-1) = ~ (b1b2.b(n-1) 1 - 0) = b1'b2 '... b (n-1)' 1 = b1'b2 '... b (n-1)' 0 + 1 = ~ x + 1. Аналогичный регистр для последнего бит равен 0. ~ (x-1) = ~ (b1b2..bi100..00 - 1) = ~ b1b2..bi011..11 = b1'b2 '.. bi '100..00 = b1'b2'.. bi'011..11 + 1 = ~ x + 1.

Ответ 4

Я попытаюсь представить интуитивное объяснение, которое каждый должен найти удобным. Если вы настаиваете, мы можем попробовать более формальный подход.

В двух дополнительных представлениях, чтобы иметь уникальное представление нулевого элемента, мы жертвуем одним положительным элементом. В результате появляется дополнительное отрицательное число, не имеющее положительного зеркала.

Итак, учитывая 2 бита, получим: {+1, 0, -1, -2}, который будет представлен в двоичном формате как:

-2    10
-1    11
 0    00
+1    01

Итак, мы можем считать нуль зеркалом. Теперь, учитывая целое число x, если мы хотим инвертировать его знак, мы можем начать с инвертирования всех битов. Этого было бы достаточно, если бы не было нуля между положительными и отрицательными. Но так как нуль делает сдвиг, в позитивах, мы компенсируем это.

Два выражения, упомянутые в вопросе, делают эту компенсацию до ~(x-1) и после ~x+1 инвертируют биты. Вы можете легко убедиться, что с использованием +1 и -1 в нашем примере с двумя битами.

Ответ 5

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

В частности, результат применения ~ к подписанному типу не определен.

Однако, насколько я знаю, все современные машины используют два дополнения для целых чисел.