| 11:04p |
Заборол дополнительный код. Действительно, код сложения остаётся таким же элегантным, как и для беззнаковых целых, а вычитание исключается вовсе.
Как можно догадаться? Без ничего - неясно, как. Но если начать с гипотезы, что некое представление отрицательных чисел (тем же битовым рядом) позволяет складывать невариабельным алгоритмом положительные и отрицательные числа и получать корректный ответ, то всё просто. Начать можно с инвертации (обратного кода), например, но выходит не то.
Вообще, лучше начать не с обращения произвольных чисел, а конкретно с единицы. Должно выполняться свойство 1 + -1 = 0, т.е. 1(0) + ?..? = (0) - в записи битов слева направо, естественно. Чтобы в нулевом бите получить 0, нужно добавить к единице 1, т.е. 1(0) + 1?..?, однако перенос даст единицу в первом бите, которую тоже надо анниглировать, т.е. 1(0) + 11?...?. И так далее, т.е. 1(0) + (1) = (0). Переполнение остаётся, ну и ладно, и неважно.
И сразу видно, что у отрицательных чисел в старших разрядах - периодическая единица. В сравнении с неотрицательными, где периодический ноль. Остальное - дело техники: единицу в периоде можно получить только инвертацией нуля в периоде. А на примере -1 видно, что нужно ещё накинуть один инкремент.
И, о чудо, а + -а = 0, и даже a + b даёт правильный результат для любых а и b. И никакого вычитания не нужно, и алгоритм сложения чётче, своп регистров не нужен, как для signed magnitude. Ибо в столбик работает вне зависимости, где стоит большее, сверху или снизу. Даже умножение практически без изменений переносится. Ну, для слов фиксированной длины ничего бы не менялось, вообще, но бесконечность этих последовательностей (= реализация на списках) вносит коррективы; здесь старший бит = бесконечный период. |