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 位无符号整数，而 a,b 是 BigInt。值以 Big Endian 样式存储在向量中。temp 是 __int64 并且进位应该作为 32 位无符号长。

假设我们从 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
...

但进位应始终为 0xffffffffff。每次为零时，结果都是'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);

不要对这些值进行硬编码。您不能保证 anunsigned long是任何特定大小（并且通常不会像您假设的那样是 64 位的）。所以位移以及您的按位“和”必须考虑到这一点。您可以将 32 替换为类似的东西sizeof(unsigned long)*8。而不是0xffffffff,~0L会做的伎俩，或者如果你觉得勇敢，也许 -1 。（只要有符号整数由二进制补码表示，它就可以工作，通常是这种情况，但标准不保证）

于 2009-11-27T14:06:28.820 回答