在下面的代码中,我使用与问题中相同的想法来实现加法和减法。唯一实际的区别是,在我的实现中,这两个函数也接受一个进位/借入位并产生一个进位/借出位。
进位位用于通过加法实现减法,该位有助于获得进位和借出位的正确值。基本上,我使用状态寄存器中的进位标志实现典型的类似 CPU 的加法和减法。
然后使用进位/借位位通过减法实现比较。我在没有运算符的情况下实现比较>=
,我也考虑算术,因为它不是按位计算的。由于使用了恢复除法算法,除法函数中需要比较函数。
我也避免使用!
运算符,^1
而是使用。
除法函数将除数作为 2 unsigned ints
,它的最重要和最不重要的部分。最后,它用余数代替最重要的部分,用商代替最不重要的部分。因此,它同时进行除法和模运算,并以典型的类似 CPU 的方式(例如 x86DIV
指令)进行处理。该函数在成功时返回 1,在溢出/除以 0 时返回 0。
main 函数做一个简单的测试。它将除法函数的结果与直接除法的结果进行比较,并在不匹配时以错误消息终止。
我unsigned long long
在测试部分使用能够测试除数 =UINT_MAX
而不会陷入无限循环。测试被除数和除数的整个值范围可能需要太多时间,这就是为什么我将它们分别设置为 0xFFFF 和 0xFF 而不是 at UINT_MAX
。
代码:
#include <stdio.h>
#include <limits.h>
unsigned add(unsigned a, unsigned b, unsigned carryIn, unsigned* carryOut)
{
unsigned sum = a ^ b ^ carryIn;
unsigned carryOuts = a & b | (a | b) & carryIn;
*carryOut = 0;
if (sum & (carryOuts << 1))
sum = add(sum, carryOuts << 1, 0, carryOut);
else
sum |= carryOuts << 1;
*carryOut |= (carryOuts & (UINT_MAX / 2 + 1)) >> (sizeof(unsigned) * CHAR_BIT - 1); // +-*/ are OK in constants
return sum;
}
unsigned sub(unsigned a, unsigned b, unsigned borrowIn, unsigned* borrowOut)
{
unsigned diff = add(a, ~b, borrowIn ^ 1, borrowOut);
*borrowOut ^= 1;
return diff;
}
unsigned less(unsigned a, unsigned b)
{
unsigned borrowOut;
sub(a, b, 0, &borrowOut);
return borrowOut;
}
int udiv(unsigned* dividendh, unsigned* dividendl, unsigned divisor)
{
int i;
unsigned tmp;
if (less(*dividendh, divisor) ^ 1/* *dividendh >= divisor */)
return 0; // overflow
for (i = 0; i < sizeof(unsigned) * CHAR_BIT; i++)
{
if (less(*dividendh, UINT_MAX / 2 + 1) ^ 1/* *dividendh >= 0x80...00 */)
{
*dividendh = (*dividendh << 1) | (*dividendl >> (sizeof(unsigned) * CHAR_BIT - 1));
*dividendl <<= 1;
*dividendh = sub(*dividendh, divisor, 0, &tmp);/* *dividendh -= divisor; */
*dividendl |= 1;
}
else
{
*dividendh = (*dividendh << 1) | (*dividendl >> (sizeof(unsigned) * CHAR_BIT - 1));
*dividendl <<= 1;
if (less(*dividendh, divisor) ^ 1/* *dividendh >= divisor */)
{
*dividendh = sub(*dividendh, divisor, 0, &tmp);/* *dividendh -= divisor; */
*dividendl |= 1;
}
}
}
return 1;
}
int udiv2(unsigned* dividendh, unsigned* dividendl, unsigned divisor)
{
unsigned long long dividend =
((unsigned long long)*dividendh << (sizeof(unsigned) * CHAR_BIT)) | *dividendl;
if (*dividendh >= divisor)
return 0; // overflow
*dividendl = (unsigned)(dividend / divisor);
*dividendh = (unsigned)(dividend % divisor);
return 1;
}
int main(void)
{
unsigned long long dividend, divisor;
for (dividend = 0; dividend <= /*UINT_MAX*/0xFFFF; dividend++)
for (divisor = 0; divisor <= /*UINT_MAX*/0xFF; divisor++)
{
unsigned divh = 0, divl = (unsigned)dividend, divr = (unsigned)divisor;
unsigned divh2 = 0, divl2 = (unsigned)dividend;
printf("0x%08X/0x%08X=", divl, divr);
if (udiv(&divh, &divl, divr))
printf("0x%08X.0x%08X", divl, divh);
else
printf("ovf");
printf(" ");
if (udiv2(&divh2, &divl2, divr))
printf("0x%08X.0x%08X", divl2, divh2);
else
printf("ovf");
if ((divl != divl2) || (divh != divh2))
{
printf(" err");
return -1;
}
printf("\n");
}
return 0;
}