非復元符号付き整数除算後の修正

Question

復元不可能な整数除算の修正後を把握できません。何らかの理由で私は訂正が必要な箇所を訂正するか、必要なときに修正しないでください。

heres擬似コード。 Dividendは16ビット、その他は8ビットです。 Dividend_Signによって、Remainder_Sign私はそれらのMSBが1であることを意味するので、2の補数で負です。

LoopCounter = 8; 
do { 
    Shift Dividend Left with 0 in LSB; 

    if (Dividend_Sign XOR Divisor_Sign) { 
     Shift 0 into Quotient; 
     DividendHighByte = DividendHighByte + Divisor; 
    } else { 
     shift 1 into Quotient; 
     DividendHighByte = DividendHighByte - Divisor; // subtraction by 2's complement 
    } 
} while (loopCounter != 0); 

Remainder = DividendHighByte; 

// here i do the Quotient conversion 
invert MSB; // shifted out anyway. Probably should be used for overflow check, not important atm. 
shift 1 into Quotient; 

今イム私は基本的に正しい答えを持っている時点で、それはただ一つの方法または別のポスト修正する必要がある...かどうか、全ての補正後。すべての訂正事例が何であるかはわかりません。今、私は半分の時間を作業イマイチ何かを持っているが、ここではとにかくです：

if (Dividend_Sign XOR Remainder_sign) {  // diff signs so correct 
    if (Remainder_Sign XOR Divisor_Sign) { // diff signs just add 
     Remainder = Remainder + Divisor; 
     Quotient = Quotient - 1; 
    } else { 
     Remainder = Remainder - Divisor; 
     Quotient = Quotient + 1; 
    } 
} 

http://en.wikipedia.org/wiki/Division_%28digital%29

http://www.acsel-lab.com/arithmetic/papers/ARITH17/ARITH17_Takagi.pdf

Answer 1

アルゴリズムの作品、問題は2の補数は、負のゼロを持っています。最後の余りが0の場合は、訂正は必要ありません。しかし、アルゴリズムはサイクル内で0の余りを検出しなければならず、遭遇した場合には常に訂正が必要である。

ちょうど0余りフラグを追加し、これをした：

if (!Remainder.isEmpty() && (zeroFlag || (Dividend.Sign() XOR Remainder.Sign()))) 
     ...do corrections