非標準基數的算術

Question

我試圖將我的arbitrary precision integer類轉換成能夠使用不是每位數8位的數字。我偶然發現了一個奇怪的問題：我可以使用uint16_t 作爲我的基本數字類型，但不能使用uint32_t。我的代碼將返回不好的結果。我用來找出錯誤的例子是0x1111111111111111 * 0x1111111111111111，應該是0x123456789abcdf00fedcba987654321。但是，我得到0x123456789abcdf0fedcba987654321。

我以爲我已經改變了所有的硬編碼類型，以便更改基本數字類型並不重要，但顯然不是。

下面是相關代碼：

typedef uint32_t       digit;   // original code uses uint8_t; uint16_t works too 
typedef uint64_t       double_digit;  // int type to hold overflow values 

typedef std::deque <digit>    base; 

const digit NEG1 = -1;     // uint8_t -> 255, uint32_t -> 4294967295 
const digit BITS = sizeof(digit) << 3; // sizeof gives the number of bytes, so multiply that by 8 to get the number of bits 
const digit HIGH_BIT = 1 << (BITS - 1); // uint8_t -> 128 

     // left bit shift. sign is maintained 
     integer operator<<(uint64_t shift){ 
      if (!*this || !shift) 
       return *this; 
      base out = digits; 
      for(uint64_t i = 0; i < (shift/BITS); i++) 
       out.push_back(0); 
      shift %= BITS; 
      if (shift){ 
       out.push_back(0); 
       return integer(out, _sign) >> (BITS - shift); 
      } 
      return integer(out, _sign); 
     } 

     // right bit shift. sign is maintained 
     integer operator>>(uint64_t shift){ 
      if (shift >= bits()) 
       return integer(0); 
      base out = digits; 
      for(uint64_t i = 0; i < (shift/BITS); i++) 
       out.pop_back(); 
      shift %= BITS; 
      if (shift){ 
       base v; 
       for(d_size i = out.size() - 1; i != 0; i--) 
        v.push_front(((out[i] >> shift) | (out[i - 1] << (BITS - shift))) & NEG1); 
       v.push_front(out[0] >> shift); 
       out = v; 
      } 
      return integer(out, _sign); 
     } 

     // operator+ calls this 
     integer add(integer & lhs, integer & rhs){ 
      base out; 
      base::reverse_iterator i = lhs.digits.rbegin(), j = rhs.digits.rbegin(); 
      bool carry = false; 
      double_digit sum; 
      for(; ((i != lhs.digits.rend()) && (j != rhs.digits.rend())); i++, j++){ 
       sum = *i + *j + carry; 
       out.push_front(sum); 
       carry = (sum > NEG1); 
      } 
      for(; i != lhs.digits.rend(); i++){ 
       sum = *i + carry; 
       out.push_front(sum); 
       carry = (sum > NEG1); 
      } 
      for(; j != rhs.digits.rend(); j++){ 
       sum = *j + carry; 
       out.push_front(sum); 
       carry = (sum > NEG1); 
      } 
      if (carry) 
       out.push_front(1); 
      return integer(out); 
     } 

     // operator* calls this 
     // Long multiplication 
     integer long_mult(integer & lhs, integer & rhs){ 
      unsigned int zeros = 0; 
      integer row, out = 0; 
      for(base::reverse_iterator i = lhs.digits.rbegin(); i != lhs.digits.rend(); i++){ 
       row.digits = base(zeros++, 0); // zeros on the right hand side 
       digit carry = 0; 
       for(base::reverse_iterator j = rhs.digits.rbegin(); j != rhs.digits.rend(); j++){ 
        double_digit prod = (double_digit(*i) * double_digit(*j)) + carry;// multiply through 
        row.digits.push_front(prod & NEG1); 
        carry = prod >> BITS; 
       } 
       if (carry) 
        row.digits.push_front(carry); 
       out = add(out, row); 
      } 
      return out; 
     } 

。有什麼明顯的，我錯過了，可能會導致不正確的計算？我一眼就看過這段代碼太久了。

完整的修改代碼是here。

編輯：我已經測試的代碼上ideone，並且它是爲這種計算返回正確的值，但我的電腦仍然沒有。這有什麼好的解釋嗎？

Answer 1

該問題似乎是由於意外的過度右移。你提到你的ideone帖子不會重現問題。在測試時，我注意到在你的ideone文章中，數字的類型實際上仍設置爲16位。當我將其改爲32位（以反映SO代碼片段）並嘗試在gcc下編譯時，我收到了一堆關於過度右移的警告。運行該程序會導致無限循環，結合右移警告和您在平臺上獲得不同行爲的事實強烈表明未定義的行爲正在發生。

更具體地說，有些地方你會得到int類型之間的位尺寸不匹配（即，你仍然有幾塊代碼需要更新）。

麻煩製造者似乎是setFromZ。這裏有Z指定的整數類型和base :: value_type指定的整數類型。二者不能保證具有相同的位數，所以當發生位不匹配時，該功能中的位移位和位掩碼代碼無法正確工作。當uint32_t是數字類型（至少在我的環境中）時，該模板的幾個實例在您的ideone代碼中發生不匹配。

編輯：確認根據標準確定過度的右移是未定義的：參考文獻：SO Post，參見接受的引用標準的答案。

（C++ 98§5.8/ 1）指出： 行爲是 未定義如果將右操作數是負的，或大於或等於 到的比特的長度推動左操作數。