Вопросы Теги

Как я могу доказать ~ (X - 1) == -X в дополнении 2? [Дубликат] 

(function () {
})();

 Это называется IIFE (Expression Exited Function Expression).  Один из знаменитых шаблонов дизайна javascript, и это сердце и душа современного модульного модуля.  Как видно из названия, он выполняется сразу после его создания.  Этот шаблон создает изолированную или личную область выполнения. 
 JavaScript до ECMAScript 6 с использованием лексического охвата, IIFE используется для имитации охвата блока.  (С блочным охватом ECMAScript 6 возможно с введением ключевого слова let и const.)  Ссылка на вопрос с лексическим охватом  
  Имитация блочного охвата с помощью IIFE  
 Преимущество производительности использования IIFE заключается в возможности передавать общеупотребительные глобальные объекты, такие как окно, документ и т. д. В качестве аргумента можно уменьшить просмотр области. (Помните, что Javascript ищет свойство в локальной области и вверх  цепочки до глобального масштаба).  Таким образом, доступ к глобальным объектам в локальной области, сокращает время поиска, как показано ниже. 
(function (globalObj) {
//Access the globalObj
})(window);
4
задан Ben Fossen 18 February 2010 в 18:36
поделиться

5 ответов

Посмотрите, что вы получаете, когда добавляете число в его побитовое дополнение. Побитовое дополнение 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.

13
ответ дан Julian Panetta 22 August 2018 в 21:48
поделиться
  • 1
    Действительно элегантное доказательство. Мне это нравится! – quinmars 17 February 2010 в 14:15
  • 2
    Это доказательство применимо к целым без знака. Для языка C вы не можете доказать результат для целых чисел со знаком, потому что это не обязательно верно. – R.. 21 September 2010 в 03:21

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

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

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

-2    10
-1    11
 0    00
+1    01

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

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

2
ответ дан Ahmed Abdelkader 22 August 2018 в 21:48
поделиться

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

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

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

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

Возможно, именно поэтому я не действительно, парень теории. : -)

6
ответ дан DigitalRoss 22 August 2018 в 21:48
поделиться
  • 1
    Я голосую за это. В стандарте C нет требования использовать дополнение 2 вообще. Это всего лишь один схем кодирования. – paxdiablo 17 February 2010 в 07:10
  • 2
    Неплохо подмечено. Вопрос может быть отредактирован, чтобы это было ясно. – Ahmed Abdelkader 17 February 2010 в 07:26
  • 3
    @paxdiablo: если целочисленный тип без знака, два дополнения не имеют значения, и это доказывается для языка C. – R.. 21 September 2010 в 03:22
  • 4
    @R, я не думаю, что это правильно. Если реализация использует дополнение, то -x точно такая же, как ~x. Если вы затем добавите один к последнему (~x + 1), то они not равны. Например, восьмибитовая компиляция для 3 - 0000-0011, ~3 - 1111-1100, ~3 + 1 - 1111-1101, которая является -2. – paxdiablo 21 September 2010 в 10:54

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

3
ответ дан malay 22 August 2018 в 21:48
поделиться
  • 1
    Я не вижу, как обращение к некоторому произвольному определению двойного дополнения каким-либо образом представляет собой доказательство алгебраического утверждения тождеств дополнения двух. Разве это не просто определение? Это похоже на «доказательство». что # ff0000 является красным, потому что это значение цвета RGB ... – DigitalRoss 17 February 2010 в 06:46
  • 2
    я не понимаю, как грубить помогает, просто голосуйте и продолжайте? – Craig 17 February 2010 в 06:56
  • 3
    Хотя этот пост не совсем ясен, в основном из-за форматирования, это совершенно правильно, и жалоба Digital Ross не подходит, я думаю. – McPherrinM 17 February 2010 в 06:59
  • 4
    Я не собирался быть грубым, и я не делал никаких попыток. Что не так с предложением, довольно точно сказать, что, поскольку мы просто определены отрицательные числа, которые должны быть представлены в 2'-дополнении, мы не можем это доказать ... потому что это аксиома. Утверждаются утверждения в терминах аксиом. Полагаю, в конечном счете доказательством может быть все, что сводится к аксиоме, но это казалось довольно близким к простому повторению. – DigitalRoss 17 February 2010 в 08:09
  • 5
    Сделать вопрос или задать серьезный вопрос не грубо. – mmcdole 17 February 2010 в 09:37

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

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

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

1
ответ дан starblue 22 August 2018 в 21:48
поделиться
  • 1
    +1 Я согласен с тем, что все современные машины используют ... & quot; но вы должны знать, что компилятор может также оптимизировать какое-либо подписанное выражение, основываясь на предположении, что он не переполняется, потому что если бы это выражение выполнялось, поведение было бы неопределенным, поэтому компилятор не должен заботиться. В lists.gforge.inria.fr/pipermail/frama-c-discuss/2009-June/&hellip приведен пример: – Pascal Cuoq 17 February 2010 в 08:29
  • 2
    Это может быть так, что все современные машины используют два дополнения, но некоторые DSP (например, Motorola 56xxx) также позволяют арифметику насыщения, так что переполнения / недостаточного потока нет. 0x7fffff + 1 == 0x7fffff, 0x800000 - 1 == 0x800000. – Dipstick 17 February 2010 в 09:13
  • 3
    @Pascal Cuoq Это замечательно. Я вижу, что это происходит в gcc 4.3.2 с -O2 или выше. Я также помещал Frama-C в список вещей, на которые нужно смотреть. – starblue 17 February 2010 в 21:37
  • 4
    Возражения и контрпримеры применяются только к подписанным целям . Поведение для целых чисел без знака, включая взаимодействие между побитовыми и арифметическими операторами, полностью определяется языком C. – R.. 21 September 2010 в 03:26
Другие вопросы по тегам:

Похожие вопросы: