Как доказать, что оператор C -x, ~x+1 и ~(x-1) дают одинаковые результаты?
Я хочу знать логику этого утверждения, доказательства. Выражения C -x, ~x+1 и ~(x-1) дают одинаковые результаты для любого x. Я могу показать, что это верно для конкретных примеров. Я думаю, что способ доказать это имеет отношение к свойствам дополнения до двух. Есть идеи?
5 ответов
Подумайте, что вы получите, когда добавите число в его побитовое дополнение. Побитовое дополнение 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.
Я не уверен, что вы можете доказать это с помощью какой-либо полезной аксиомы, кроме довольно тривиального сокращения, до того факта, что мы определили отрицательные числа в современных целочисленных ALU, чтобы они были дополнением до двух.
Компьютеры не должны быть реализованы с двумя дополнительными бинарными аппаратными средствами, просто есть различные привлекательные свойства, и почти все построено таким образом в наши дни. (Но не с плавающей точкой! Это дополнение!)
Таким образом, мы строим машину, которая будет представлять отрицательные числа в дополнении 2. Выражения, которые показывают отрицательные числа, которые должны быть представлены в дополнении к двум, точны, но только потому, что мы определили их таким образом. Это аксиоматическая основа для отрицательных целых чисел в современных машинах.
Поскольку мы определяем отрицание в терминах дополнения к двум, вы, по сути, имеете в виду аксиомы, хотя я полагаю, что именно это в итоге и делают все доказательства.
Может быть, поэтому я не теоретик.:-)
~x+1 эквивалентно дополнению + 1 (т.е. отрицательному числу) к 2 представлению -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.
Я постараюсь представить интуитивно понятное объяснение, которое каждый должен найти удобным. Если вы настаиваете, мы можем попробовать более формальный подход.
В представлении дополнения до двух, чтобы иметь уникальное представление нулевого элемента, мы жертвуем один положительный элемент. В результате появляется дополнительное отрицательное число, которое не имеет положительного зеркала.
Итак, учитывая 2 бита, мы получаем: {+1, 0, -1, -2} который будет представлен в двоичном виде как:
-2 10
-1 11
0 00
+1 01
Таким образом, мы можем думать о нуле как о зеркале. Теперь, учитывая целое число x, если мы хотим инвертировать его знак, мы можем начать с инвертирования всех битов. Этого было бы достаточно, если бы между положительными и отрицательными значениями не было нуля. Но так как ноль делает сдвиг, в позитивах, мы должны это компенсировать.
Два выражения, упомянутые в вопросе, делают эту компенсацию раньше ~(x-1) и после ~x+1 инвертировать биты. Вы можете легко проверить это, используя +1 а также -1 в нашем 2-битном примере.
В целом это не так, поскольку стандарт C не требует использования дополнения до двух для представления отрицательных чисел.
В частности, результат применения ~ к подписанному типу не определен.
Однако, насколько я знаю, все современные машины используют двойное дополнение для целых чисел.