Сдвиг вправо числа сохранения

Question

Арифметика сохранения при переносе использует удвоенное количество битов: одно слово для хранения "виртуальной суммы", другое - для "виртуального переноса", чтобы избежать распространения переноса, который является ограничивающим фактором в аппаратной скорости.

У меня есть система, которая требует деления этих чисел на степени двух, но просто смещение вправо обоих чисел не работает во всех случаях, например. два 16-битных числа сохранения переноса, которые вы добавляете для получения 4000, C001 - это виртуальная сумма, 7FFF - это виртуальный перенос.

C001 + 7FFF = 4000  (discard overflow bits)
but after right shift
6000 + 3FFF = 9FFF   (when it should be 2000)

Вкратце: как вы делите число сохраняемых переносов на степень два? (Сохраняя номер для переноса)

Answer 1

Во-первых, смещение вправо на 1 фактически приводит к удалению на 2 с забыванием остатка. Но остаток может понадобиться для получения точного результата. Например, измените исходный пример, добавив C000 к 8000 или C002 к 7FFE. Оба дают одинаковую сумму, но сумма смещенных значений равна A000 вместо вашего 9FFF, и это определенно более правильно. Таким образом, вы можете сделать такое смещение, только если сумма младших битов может быть потеряна. В вашем случае с 2 слагаемыми и 1 битным сдвигом это означает, что не более 1 слагаемого может иметь 1 в своем LSB.

Во-вторых, считайте, что это исправлено, и у вас есть A000. Простая идеальная математика гласит: (a+b)/2 == a/2 + b/2. Для вашего случая бит переноса, который вы изначально игнорировали, весил 0x10000, но после сдвига на 1 он весит 0x8000. Это именно то, чем A000 отличается от вашего ожидаемого 2000 года. Итак, если вы уверены в других аспектах вашего метода, завершите его логическим И с ~0x8000 == 0x7FFF.

Answer 2

Существует методика коррекции представления таким образом, чтобы оно было смещаемым. Это происходит из статьи Тобиаса Нолла "Переносимые архитектуры для высокоскоростной цифровой обработки сигналов". Вы можете вычислить новые знаковые биты векторов переноса и суммирования как

c '= c_out

s '= s xor c xor c_out

где s и c - исходные биты знака, а c_out - отброшенный бит переноса из дополнения переноса-сохранения.