Есть ли способ уловить переполнение / недополнение во время двоичного умножения, используя алгоритм Бута?

Question

Я пытаюсь найти способ уловить переполнение / недостаточность точно при умножении двух двоичных чисел со знаком (a и b) на n произвольных битов эффективным способом.Я использую дополнение 2.

Есть ли способ сделать это во время выполнения алгоритма стенда?Если так, то как?

Вещи, которые я рассмотрел, но не могу использовать:

1. Обнаружение переполнения в GCC : поскольку мой сценарий использования имеет дело с произвольной длиной битовкоторые могут или не могут быть преобразованы в базовые целочисленные типы со знаком.

2. Проверка после умножения с использованием деления : впоследствии я не хочу использовать деление для проверкирезультат r с r / b == a.Это было бы слишком дорого в вычислительном отношении.

3. Традиционное умножение с добавлением : слишком вычислительно неэффективно.

---

Toнемного поясним, как я подошел к алгоритму Бута здесь, шаг за шагом, на нескольких примерах, используя n = 8 битов с прямым порядком байтов для обеспечения удобства чтения.

Добавлен бит 'booth'в регистр справа и слева добавляется дополнительный бит для обработки предела отрицательного целого.

, поэтому структура регистра:

 x                     q
|.|.... ....|.... ....|.|

, где x = дополнительныйбит и q бит "будка".Таким образом, общий размер составляет 8 + 8 + 2 бита.

eg1:

a: 0000 0101 (5)
b: 1111 1101 (-3)

       m: 0|0000 0101|0000 0000|0 (a)
      -m: 0|1111 1011|0000 0000|0 (negated a)
register: 0|0000 0000|1111 1101|0 (initialized register with b)

step 1 (p+=-m): 0|1111 1011|1111 1101|0
step 1 (shift): 0|0111 1101|1111 1110|1
step 2 (p+=+m): 0|1000 0010|1111 1110|1
step 2 (shift): 0|0100 0001|0111 1111|0
step 3 (p+=-m): 1|0011 1100|0111 1111|0
step 3 (shift): 0|1001 1110|0011 1111|1
step 4 (shift): 0|0100 1111|0001 1111|1
step 5 (shift): 0|0010 0111|1000 1111|1
step 6 (shift): 0|0001 0011|1100 0111|1
step 7 (shift): 0|0000 1001|1110 0011|1
step 8 (shift): 0|0000 0100|1111 0001|1

result:         .|.... ....|1111 0001|. = -15 //Cool

eg2:

a: 0011 1111 (63)
b: 1111 1101 (-3)

       m: 0|0011 1111|0000 0000|0 (a)
      -m: 0|1100 0001|0000 0000|0 (negated a)
register: 0|0000 0000|1111|1101|0 (initialized register with b)

step 1 (p+=-m):  0|1100 0001|1111 1101|0
step 1 (shift):  0|0110 0000|1111 1110|1
step 2 (p+=+m):  0|1001 1111|1111 1110|1
step 2 (shift):  0|0100 1111|1111 1111|0
step 3 (p+=-m):  1|0001 0000|1111 1111|0
step 3 (shift):  0|1000 1000|0111 1111|1
step 4 (shift):  0|0100 0100|0011 1111|1
step 5 (shift):  0|0010 0010|0001 1111|1
step 6 (shift):  0|0001 0001|0000 1111|1
step 7 (shift):  0|0000 1000|1000 0111|1
step 8 (shift):  0|0000 0100|0100 0011|1

result:          .|.... ....|0100 0011|. = 35 //Wrong! underflow.

Спасибо.