使用按位運算符在C++中恢復分區實現

我試圖實現the restoring division algorithm，但我一直得到不正確的結果。訣竅是我的任務要求我只使用按位運算符，循環和分支來實現+， - ，*，/，％。我已成功實施add(a,b),sub(a,b)和mul(a,b)，因此在我的div(a,b,&rem)方法中使用它們。下面的代碼，使用按位運算符在C++中恢復分區實現

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？

來源

2017-09-08 Dando18

什麼類型的參數？您是否注意到維基百科代碼中的評論：** P和D需要兩倍於N和Q的字寬** – Barmar

@Barmar在我的實現中'T'是一個短的 – Dando18

您需要仔細檢查算法。您的if(q < 0)比較使用了錯誤的變量。它應該是if (remainder < 0)。

來源

2017-09-08 21:55:51 1201ProgramAlarm

謝謝我沒有抓到，但是，米仍然得到不正確的結果。 – Dando18

使用按位運算符在C++中恢復分區實現

回答

相關問題