使用按位运算符在C++中恢复分区实现

Question

我试图实现the restoring division algorithm，但我一直得到不正确的结果。诀窍是我的任务要求我只使用按位运算符，循环和分支来实现+， - ，*，/，％。我已成功实施add(a,b),sub(a,b)和mul(a,b)，因此在我的div(a,b,&rem)方法中使用它们。下面的代码，

template<typename T> 
T div(T dividend, T divisor, T &remainder){ 
    unsigned q = 1; 
    unsigned n = mul(sizeof(T), CHAR_BIT); 
    remainder = dividend; 
    divisor <<= n; 

    for(int i=sub(n,1); i>=0; i=sub(i,1)) { 
     remainder = sub(remainder << 1, divisor); 
     if(remainder < 0) { 
      q &= ~(1 << i); // set i-th bit to 0 
      remainder = add(remainder, divisor); 
     } else { 
      q |= 1 << i;  // set i-th bit to 1 
     } 
    } 
    return q; 
} 

我测试过的所有边缘案件和常见的例子为add，sub，并且mul我知道他们正常工作的任何整数输入。

看来，对于任何输入我得到q = -1和remainder = 0。我认为这个问题与签署T或q和n有关。我认为我的实现是一样的，有没有原因为什么该方法返回-1和0？

Answer 1

您需要仔细检查算法。您的if(q < 0)比较使用了错误的变量。它应该是if (remainder < 0)。