gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-02 10:23:49 25 4
gpt4 key购买 nike

我试图找到一种有效地将a任意位的两个带符号二进制数(bn)相乘的准确捕获上溢/下溢的方法。我正在使用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.

    谢谢。

    最佳答案

    -3 by 63 Multiplication using Booth's Algorithm


    -3 by 63 Multiplication using Booth's Algorithm

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


    63 by -3 Multiplication using Booth's Algorithm

    关于c++ - 是否有办法使用Booth算法捕获二进制乘法期间的上溢/下溢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55449923/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com