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

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 位移位器。关于如何调整上面的代码以反射(reflect)我的硬件功能的任何建议？给定代码每次迭代仅移动 1 位。

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

Answer 1

移动多个位的能力不会有太大帮助，除非你有硬件乘法，比如 8 位 x 8 位，或者你可以负担得起一些 RAM/ROM 来做(比如)4 位4 位乘以查找。

可以通过交换参数使乘数更小来帮助直接移位和加法(正如您正在做的那样)。

如果您的机器通常在处理 16 位的事情时速度更快，那么将您的 32 位 'a' 一次视为 'a1:a0' 16 位，类似地 'b'，您也可以这样做一些周期。您的结果只有 32 位，因此您不需要执行 'a1 * b1' - 尽管其中一个或两个可能为零，因此胜利可能不大!此外，您只需要 'a0 * b1' 的 ls 16 位，这样就可以完全用 16 位完成——但是如果 b1(假设 b <= a)通常为零，这也不是什么大赢家。对于“a * b0”，您需要一个 32 位的“a”和 32 位加到“answer”中，但您的乘数仅为 16 位...这可能有帮助也可能没有帮助。

跳过乘数零的运行可能会有所帮助——取决于处理器和乘数的任何属性。

FWIW:根据我的小经验，做魔术 'a1*b1'、'(a1-a0)*(b0-b1)'、'a0*b0' 并通过移位、加法和减法组合结果，绝对的噩梦……必须尊重“(a1-a0)”、“(b0-b1)”及其产品的标志，这让看似可爱的把戏变得有些困惑。当你完成它和加法和减法时，你必须有一个强大的慢乘法才能使这一切都值得!当乘以非常非常长的整数时，这可能会有所帮助......但内存问题可能会占主导地位......当我尝试它时，它有点令人失望。