0

私は独自の小さな多精度ライブラリを作成しています。減算のメソッドを作成しているときに、奇妙なエラーが発生しました。これは、多精度減算のために私が書いたコード ブロックです。

/* subtraction */
 for (; p_aReverseIter != a.m_elements.rend(); ++p_aReverseIter, ++p_bReverseIter) 
 {
  temp = static_cast<__int64>(static_cast<__int64>(p_aReverseIter->m_Value) - 
         static_cast<__int64>(p_bReverseIter->m_Value) + 
         (carry));
  --- debug output-  
  p_aReverseIter->m_Value = static_cast<unsigned int>(temp & 0xffffffff); 
  carry = static_cast<unsigned long>(temp >> 32);

 }

p_aReverseIter->m_Value は 32 ビットの unsigned int ですが、a、b は BigInt です。値は、ビッグ エンディアン スタイルでベクター内に格納されます。temp は __int64 で、キャリーは 32 ビットの unsigned long として機能する必要があります。

a から b を減算するとします。a > b (符号なし減算) ですが、b のすべての 32 ビット ワードは a よりも大きくなります。このルーチンは、次の出力を生成します。

a = 0xfefefefe (10 elem) 0xfefefefe (10 elem) 0xfefefefe (10 elem) 
0xfefefefe (10 elem) 

b = 0x12 (2 elem) 0x12121212 (9 elem) 0x12121212 (9 elem) 0x12121212 
(9 elem) 0x12121212 (9 elem)

a[i]: 12121212 
b[i]: fefefefe 
old carry: 0 
temp = a - b + carry: ffffffff13131314
Value: 13131314 
new carry: ffffffffffffffff

a[i]: 12121212 
b[i]: fefefefe 
old carry: ffffffff 
temp = a - b + carry: 13131313 
Value: 13131313 
new carry: 0

a[i]: 12121212 
b[i]: fefefefe 
old carry: 0 
temp = a - b + carry: ffffffff13131314 
Value: 13131314 
new carry: ffffffffffffffff

a[i]: 12121212 
b[i]: fefefefe 
old carry: ffffffff 
temp = a - b + carry: 13131313 
Value: 13131313 
new carry: 0
...

ただし、キャリーは常に 0xffffffff でなければなりません。ゼロになるたびに、結果は間違っている '13131314' になります。次に、キャリーを unsigned long から unsigned __int64 に変更し、

carry = static_cast<unsigned long>(temp >> 32);

に

carry = static_cast<unsigned __int64>(temp >> 32);

キャリーは常に正しく計算され、0xffffffff に設定されるようになりました。しかし、2^32 の 64 ビット値を右シフトすると、常に 32 ビットの結果が生成されます。

私の質問は、さまざまな結果を理解するために、何が欠けているのでしょうか?

どうもありがとうございました。

4

2 に答える 2

3

sizeof(long)あなたの環境には何がありますか？テストすると、4 であることがわかると思います。つまり、unsigned long実際には 32 ビット値です。

于 2009-11-27T13:50:32.863 に答える
0 
  p_aReverseIter->m_Value = static_cast<unsigned int>(temp & 0xffffffff); 
  carry = static_cast<unsigned long>(temp >> 32);

このような値をハードコーディングしないでください。unsigned longanが特定のサイズであることは保証されていません(また、多くの場合、想定どおりに 64 ビットではありません)。したがって、ビットシフトとビットごとの「and」はそれを考慮に入れる必要があります。sizeof(unsigned long)*832 をおそらく次のようなものに置き換えることができます。そして の代わりに0xffffffff,~0Lうまくいくか、勇気があるならおそらく -1 です。(signed int が 2 の補数で表されている限り機能しますが、これは通常のケースですが、標準では保証されていません)

于 2009-11-27T14:06:28.820 に答える