在没有算术运算符的情况下执行位除
我正在尝试完成一项任务，要求我为二进制算术编写三个函数。 badd（）是为我提供的，所以我用它来帮助编写bsub（）和bmult（）函数。 但是，我无法理解如何执行bdiv（）函数。 我知道我需要使用右移和我的bsubb（）函数迭代这些位，但我不知道如何实现它。 以下是我到目前为止所写的function。 如果您发现我在写它们时犯了任何错误（请注意bsub（）和bmult（）），请告诉我。 谢谢。
/** This function adds the two arguments using bitwise operators. Your * implementation should not use arithmetic operators except for loop * control. Integers are 32 bits long. This function prints a message * saying "Overflow occurred\n" if a two's complement overflow occurs * during the addition process. The sum is returned as the value of * the function. */ int badd(int x,int y){ int i; char sum; char car_in=0; char car_out; char a,b; unsigned int mask=0x00000001; int result=0; for(i=0;i<32;i++){ a=(x&mask)!=0; b=(y&mask)!=0; car_out=car_in & (a|b) |a&b; sum=a^b^car_in; if(sum) { result|=mask; } if(i!=31) { car_in=car_out; } else { if(car_in!=car_out) { printf("Overflow occurred\n"); } } mask<<=1; } return result; } // subracts two integers by finding the compliemnt // of "y", adding 1, and using the badd() function // to add "-y" and "x" int bsub(int x, int y){ return badd(x, badd(~y, 1)); } //add x to total for however many y int bmult(int x,int y){ int total; int i; for(i=0; i < = y; i++) { total = badd(total,x) } return total; } // comment me unsigned int bdiv(unsigned int dividend, unsigned int divisor){ // write me return 0; } 这里不多说，它只是base-2中的一些基本数学：
unsigned int bmult(unsigned int x, unsigned int y) { int total = 0; int i; /* if the i-th bit is non-zero, add 'x' to total */ /* Multiple total by 2 each step */ for(i = 32 ; i >= 0 ; i--) { total <<= 1; if( (y & (1 << i)) >> i ) { total = badd(total, x); } } return total; } unsigned int bdiv(unsigned int dividend, unsigned int divisor) { int i, quotient = 0, remainder = 0; if(divisor == 0) { printf("div by zero\n"); return 0; } for(i = 31 ; i >= 0 ; i--) { quotient <<= 1; remainder <<= 1; remainder |= (dividend & (1 << i)) >> i; if(remainder >= divisor) { remainder = bsub(remainder, divisor); quotient |= 1; } } return quotient; }
这两篇文章足以编写这些样本： Div和Mul 。
在下面的代码中，我使用与问题中相同的想法实现加法和减法。 唯一的实际区别在于，在我的实现中，这两个函数还接受一个进位/借位，并产生一个进位/借出位。
进位位用于通过加法实现减法，该位有助于获得进位和借位的正确值。 基本上，我使用状态寄存器中的进位标志实现典型的类似CPU的加法和减法。
然后使用进位/借位来通过减法实现比较。 我在没有>=运算符的情况下实现比较，我也考虑算术运算，因为它的性质不太明显。 由于使用了恢复除法算法，因此在除法函数中需要比较函数。
我也避免使用了! 运算符并使用^1代替。
除法函数将除数作为2个unsigned ints ，它是最重要和最不重要的部分。 最后，它用剩余部分取代最重要的部分，用商部分取最不重要的部分。 因此，它执行除法和模运算，并以典型的CPU方式（例如x86 DIV指令）执行它们。 该函数在成功时返回1，在溢出/除0时返回0。
主要function做了一个简单的测试。 它将除法函数的结果与直接除法的结果进行比较，并在不匹配时终止错误消息。
我在测试部分使用unsigned long long来测试divisor = UINT_MAX而不会陷入无限循环。 测试被除数和除数的整个值范围可能需要太多时间，这就是为什么我将它们分别设置为0xFFFF和0xFF而不是UINT_MAX 。
码：
#include #include 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; }
- 而dividend
- 现在检查除数中的位数是否等于被除数中的位数，移位除数为左，直到被除数中的位数等于除数中的位数。
- 现在减去被除数，除数并将1加到商，确保你在正确的位置有一个商（如小数位）
重复此过程，直到被除数为0或1