位乘以16
我正在写一个使用移位和加法的软乘法函数调用。 现有的函数调用如下所示：
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（无符号长整型）== 32位
基本的方法是（假设换成1）： -
取决于您的硬件...
但你可以尝试： -
然后 ：-
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;
}
然后按相反方向进行右移
使用以下方法进行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)
如果P是一个2的方便权力（例如2 ** 16,2 ** 32），所以乘以它就是一个快速转换。 这样可以将小数从4减少为3，并且递归地将O（N **（3/2））代替为O（N ** 2）。
至少在Knuth的TAoCP中描述了该方法。 这里有更多高级版本。
对于小数字（例如8乘8位），如果您有足够的快速ROM，则以下方法很快：
a * b = square(a+b)/4 - square(a-b)/4
如果要制表int(square(x)/4) ，则需要1022个字节用于无符号乘法，510个字节用于带符号乘法。
上面的代码正在以传统的方式相乘，即我们在小学中学到的方式：
EX：
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;
}
这是昂贵的，但它可以满足你的需求，无论如何，如果你有更多的限制（比如计算时间......），你可以考虑其他方法。
链接地址: http://www.djcxy.com/p/72613.html