Что делать с переполнением дополнительного кода числа после умножения?

Question

[asault_ceko]

Умножаю два отрицательных числа в дополнительном коде. В конце алгоритма у меня переполнение 11 перед запятой. Что в таком случае делать? Я же не могу просто перевести в прямой код.

Answer 1

[Mercury13]

В случае, если N=2^b, тогда
(N+y)(N+v) = N²−N(|y|+|v|)+yv ≡ yv (mod N), и, таким образом, можно множить дополнительные коды, растянув их до длины N².
Как поступать, не растягивая? — ну, добавить N(|y|+|v|), наверное.
Итак, ваши числа ДЕВЯТИбитные (N=512), и символизируют y=−217, v=−161. Ну, соответственно N+y=295, N+v=351.
(N+y)(N+v) + N(|y|+|v|) = 295·351 + 512·(217+161) = 297081,
N² = 262144,
Выкинем один переполненный бит 297081−262144 = 34937,
Ну что, есть у нас (−217)·(−161)?

Что вы неправильно сделали…
1. Я не понимаю, что здесь делают 2(|y|+|v|).
2. Числа у нас ДЕВЯТИбитные, так что и начальные единицы нельзя выкидывать, и сдвиг должен быть на девять бит, а не на восемь или десять.

Если попробовать отрубить знаковый бит и N²=65536…
N=256, y=−217, v=−161, N+y=39, N+v=95.
(N+y)(N+v) + N(|y|+|v|) = 39·95 + 256·(217+161) = 100473,
вычтем переполненный бит 100473−65536=34937
Но тогда придётся выкинуть ОБЕ начальных единицы, а сдвиг делать на 8.
С отрубленными знаковыми битами только знание, что оба числа отрицательные, позволяет трактовать эти 34937 как 16-битное беззнаковое. А то мы же отрубили все признаки этого, верно?

А то вы одну выкинули, а другую оставили.

Comments

[asault_ceko]

Мой косяк. Понимаю. Я взял числа из другого задания. Теперь я поставил дополнительный код наших чисел и выполнил умножение по алгоритму, затем добавил корректировку C. Потому что если мы умножаем два числа в дополнительном коде, то умножаем их по алгоритму, а затем добавляем корректировку 2(|X|+|Y|). Теперь нормально умножил, но теперь у меня переполнение 100. Куда его деть?

[Mercury13]

1. Повторяю, переполненный бит просто уходит.
2. Я не вижу 295·351 = 1'1001'0100'0111'1001₂. Проверяйте умножение.
3. Корректировка |X|+|Y| должна идти со сдвигом в 9 бит. А не 11.

[Mercury13]

4. 295·351 само по себе не должно делать переполнения (у нас ВОСЕМНАДЦАТЬ бит рабочих и один переполненный). И даже один бит, как видите, в запасе. Только когда сложим, один бит переполнится и его выкинем.

Answer 2

[Zerg89]

https://www.cyberforum.ru/informatics/thread175777...