ビットワイズ演算子を使用したC++での除算の実装の復元

Question

the restoring division algorithmを実装しようとしていますが、結果が不正確です。私が+、 - 、*、/、％をビット演算子、ループ、ブランチだけを使って実装する必要があります。 add(a,b)、sub(a,b)、およびmul(a,b)を正常に実装しました。そのため、私のdiv(a,b,&rem)メソッドで使用しました。ここで私はadd、sub、およびmulのすべてのエッジケースと一般的な例をテストしてみた

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; 
} 

コードは、だと私は、彼らは任意の整数入力のために正常に動作知っています。

どの入力に対しても、q = -1とremainder = 0が表示されます。問題はT、またはqとnの署名と関係があると思います。私の実装は同じだと思うが、その方法が-1と0を返す理由はあるのだろうか？

Answer 1

もう少しアルゴリズムをチェックする必要があります。 if(q < 0)の比較で間違った変数が使用されています。 if (remainder < 0)である必要があります。