32位乘法通过16位移位实现

Question

我正在编写一个使用移位和加法的软件乘法函数调用。现有的函数调用如下：

unsigned long __mulsi3 (unsigned long a, unsigned long b) {

    unsigned long answer = 0;

    while(b)
    {
        if(b & 1) {
            answer += a;
        };

        a <<= 1;
        b >>= 1;
    }
    return answer;
}

尽管我的硬件没有乘法器，但我有一个硬位移器。这个位移器可以一次性向上位移16位。

如果我想充分利用我的16位位移器，你有什么建议可以使以上代码反映出我的硬件的能力呢？给定的代码每次只位移1位。

16位位移器可以一次性将32位无符号长整型值向上位移16个位置。sizeof(unsigned long) == 32位。

- Jon J

---

那么，在你的机器上，sizeof(unsigned long) == 4 && CHAR_BIT == 8吗？值得指出的是，由于我主要在64位上工作，所以对我来说默认情况下sizeof(unsigned long) == 8，可能也是很多其他人的情况。你的16位移位器只能移动16位（unsigned short，还是unsigned int？）数量，而不是32位数量？或者它可以一次将32位unsigned long值移动16个位置？还是其他什么？ - Jonathan Leffler

谢谢您帮助我更好地梳理我的问题。在您指出之前，我从未想过这个问题。 - Jon J

直到你指出来，我才意识到自己没有很精确。事实如下：16位移位器可以一次将32位无符号长整型值向左移动16位。sizeof(unsigned long) == 32 bits。 - Jon J

Answer 1

能够同时移动多个位并不会有太大的帮助，除非你拥有硬件乘法器，比如8位x8位，或者你可以负担一些RAM/ROM来进行（比如）4位x4位的查找乘法。您正在执行的直接移位和加法可以通过交换参数以使乘数更小来得到帮助。

如果您的机器通常在16位事务中运行得更快，则将您的32位“a”视为每次16位的“a1:a0”，并类似地处理“b”，您可能只需要同样一些周期。结果仅为32位，因此您不需要执行“a1 * b1”--尽管其中一个或两个可能为零，因此胜利可能不大！对于“a0 * b1”的ls 16位，您只需要16位即可完成--但是如果b1（假设b <= a）通常为零，则这也不是很重要。对于“a * b0”，您需要一个32位的“a”和32位的加法器加入到“answer”中，但是您的乘法器仅为16位...这可能有所帮助。

跳过连续的乘数零可能有所帮助--具体取决于处理器和乘数的任何属性。

顺便说一句：根据我的小经验，“a1*b1”、“（a1-a0）*（b0-b1）”、“a0*b0”和通过移位、加法和减法组合结果是绝对的噩梦...必须尊重“(a1-a0)”、“（b0-b1）”及其乘积的符号，这使得看起来很可爱的技巧变得有些混乱。当您完成所有这些操作并进行加减运算时，您必须拥有非常缓慢的乘法才能使所有操作都值得！在乘以非常长的整数时，这可能会有所帮助...但是在那里，内存问题可能会占主导地位...当我尝试时，它让人有些失望。

- user3793679

Answer 2

拥有16位移位可以帮助您使用以下方法进行微小的速度增强：

(U1 * P + U0) * (V1 * P + V0) =
= U1 * V1 * P * P + U1 * V0 * P + U0 * V1 * P + U0 * V0 =
= U1 * V1 * (P*P+P) + (U1-U0) * (V0-V1) * P + U0 * V0 * (1-P)

提供方便的2的幂次方（例如2 ^ 16，2 ^ 32）作为P，因此将其乘以可以快速移位。这将从较小数字的4个乘法减少到3个乘法，并且对于非常长的数字，递归地减少到O（N ^ 1.58）而不是O（N ^ 2）。

这种方法被命名为 Karatsubaʼs multiplication。那里描述了更高级的版本。

对于小数字（例如8位x 8位），如果您拥有足够快速的ROM，则以下方法很快：

a * b = square(a+b)/4 - square(a-b)/4

如果要制表 int(square(x)/4)，则需要1022字节的无符号乘法和510字节的有符号乘法。

- Netch

---

OP想要一个截断的C乘法（32x32 => 32位），而不是完整的乘法（32x32 => 64位）。因此，我们可以将P=2^16的P*P项删除。我认为user3793679是正确的，假设在32位值上操作是有效的，那么这里可能没有任何收益。除非你像你建议的那样使用LUT进行小乘法，那么也许会有一些收益。 - Peter Cordes

Answer 3

基本方法是（假设移位1）：

• 移动前16位
• 将前16位的最低位设置为后16位的最高位
• 移动后16位

这有点取决于您的硬件...

但您可以尝试：

• 假设unsigned long是32位
• 假设大端字节序

然后：

 union Data32
        {
           unsigned long l;
           unsigned short s[2];
        }; 

unsigned long shiftleft32(unsigned long valueToShift, unsigned short bitsToShift)
{
    union Data32 u;
    u.l  = valueToShift
    u.s[0] <<= bitsToShift;
    u.s[0] |= (u.s[1] >> (16 - bitsToShift);
    u.s[1] <<= bitsToShift

    return u.l;
}

然后对于向右移位，以相同的方式进行反向操作。

- Keith Nicholas

Answer 4

上面的代码是按照传统的方式进行乘法运算的，就像我们在小学学到的那样：

例如：

    0101
  * 0111
  -------
    0101
   0101.
  0101..
 --------
  100011

当然，如果你没有乘法运算符或1位移位器，你不能像那样处理它！不过，你可以用其他方法来做，例如使用循环：

unsigned long _mult(unsigned long a, unsigned long b)
{
    unsigned long res =0;

    while (a > 0)
    {
        res += b;
        a--;
    }

    return res;
} 

虽然成本高昂，但它能满足您的需求，如果您有更多限制（如计算时间...），可以考虑其他方法。

- chouaib

---

OP有一个移位器，可以在一次操作中将32位数字向上移动16位。他们想知道是否可以通过使用更大的移位来改进现有的乘法例程，该例程一次只能移动1位。 - Gabe