Реализация вычитания в Nand2tetris

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

opMinus = addition <> notX <> notOut

Я не мог найти никакого объяснения этому в Интернете. И последний шаг, когда я пытаюсь вывести это сам, выглядит ерундой, хотя quickcheck говорит, что это правильно:

a - b
a + !b + 1 -- 2s complement
!!(a + !b + 1) -- double negation
!(!a + b) -- apparently this is correct and i have no clue why

Последний шаг кажется основанным на чем-то вроде

!(a+b) == !a + !b + 1

но у меня нет интуиции, почему это работает, поэтому объяснение было бы очень признательно. Спасибо за чтение!


bit-manipulation nand2tetris
person Taren    schedule 20.04.2019    source источник
comment
Чтобы вычесть b из a, измените знак b (переверните биты и прибавьте 1) и сложите.   -  person Marichyasana    schedule 20.04.2019

Ответы (3)


arrow_upward
1
arrow_downward

Один из способов взглянуть на это более интуитивно, а не просто алгебраически, — это рассмотреть действие побитового дополнения на всей числовой прямой, то есть симметрично перевернуть ее. !a + b затем добавляет b в этот перевернутый контекст, а последний ! переворачивает все обратно. Шаг на одну единицу «вперед» (так, b = 1) в перевернутом контексте означает один шаг назад в обычном контексте и так далее.

Такой тип «перевернуть, действие, перевернуть» эффективно поворачивает действие в середине от направления, в котором оно обычно работает, есть и другие примеры принципа, иногда с перевернутыми обоими аргументами, например min(a, b) = !max(!a, !b).

person harold    schedule 20.04.2019
comment
Я не понял, почему он сделал шаг вперед, но, глядя на !(a+b) как на -(a+b)-1, это становится очевидным в ретроспективе. - person Taren; 20.04.2019

arrow_upward
1
arrow_downward

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

Поскольку некоторые процессоры на самом деле имеют чипы, которые принимают сигнал для переключения сумматоров на вычитатели (лучше сказать, что их транзисторы расположены таким образом, чтобы это допускалось), а nand2tetris не имеет, вам на самом деле нужно отрицайте число, которое вы вычитаете (b). Чтобы сделать это в двоичном коде, вам НЕ нужно. Если бы жизнь была простой, это был бы твой последний шаг.

Возьмем, однако, это, например. Скажи, что ты программируешь. Вы используете подписанный 8-битный int для хранения значения b.

Это означало бы, что !b = -(b). Итак, если b=127, !b = -(127+1) = -128. Чтобы исправить это, вы добавляете 1 к !b, чтобы получить правильное значение -127. Теперь мы подошли к правильному числу, которое намеревались вычесть, поэтому мы можем перейти к добавлению b к a (число, которое мы хотим вычесть из). Если a = 1 и b = 127, если мы сделаем a + !(b) + 1, в результате вы получите -126, поскольку 1 + (-128) + 1 = 2-128 = -126.

Также обратите внимание, что пока я использовал ! для представления НЕ, фактическая побитовая операция ~. Это называется комплиментом 2, и вы можете узнать больше об этом здесь: https://en.wikipedia.org/wiki/Two%27s_complement

Редактировать: убрал ошибку.

person SirGouki    schedule 08.08.2020

arrow_upward
0
arrow_downward

Поиграв с этим еще немного, я понял это:

(a-b)
!!(a-b)            | double bitwise not is id
!(!(a-b)+1-1)      | +1-1 is id
!(-(a-b)-1)        | !(a-b)+1 = -(a-b)
!(-a + b - 1)      | distribute the negation
!(!a + 1 + b - 1)  | -a = !a+1
!(!a + b)
person Taren    schedule 20.04.2019
comment
Да, так часто процесс постановки (и записи) вопроса является семенем ответа. Поздравляю с разгадкой! - person MadOverlord; 20.04.2019