c++ - 是否有办法使用Booth算法捕获二进制乘法期间的上溢/下溢？

Question

我试图找到一种有效地将a任意位的两个带符号二进制数(b和n)相乘的准确捕获上溢/下溢的方法。我正在使用2的补码。

在执行展位的算法期间，是否可以这样做？如果是这样，怎么办？

我考虑过但不能使用的东西:

GCC的内置溢出检测:由于我的用例处理的是任意位长度，该位长度可以或可以不转换为基本带符号整数类型。

使用除法的乘法后检查:我不希望事后使用除法来使用r检查结果r / b == a。那将在计算上过于昂贵。

增加的传统乘法:计算效率太低。

为了使我更清楚地了解Booth的算法，这里逐步介绍了使用n = 8bits大端数据保持可读性的几个示例。

“booth”位添加到右侧的寄存器中，并在左侧添加了用于处理负整数限制情况的额外位。

因此寄存器结构为:

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

其中x =多余的位，q的“展位”位。因此，总大小最终为8 + 8 + 2位。

例如1:

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

例如2:

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.

谢谢。

Answer 1

-3 by 63 Multiplication using Booth's Algorithm

63 by -3 Multiplication using Booth's Algorithm.
In this case, sign bit will be ignored.