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

Question

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

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

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

Answer 1

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

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

Answer 2

После игры с этим я еще разобрался:

(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)