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

Question

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

Answer 1

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

x + ~ x = 0b11 ... 11 (n-битное значение всех единиц)

Независимо от количества бит в х. Кроме того, обратите внимание, что добавление единицы к 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.

Answer 2

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

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

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

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

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

Answer 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.

Answer 4

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

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

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

-2    10
-1    11
 0    00
+1    01

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

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

Answer 5

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

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

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