c++ - 非标准基础中的算术

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 位(以反射(reflect) SO 代码片段)并尝试在 gcc 下编译时，我收到了一堆关于过度右移的警告。运行该程序导致无限循环，结合右移警告以及您在平台上获得不同行为的事实强烈表明正在发生未定义的行为。

更具体地说，在某些地方，您会遇到 int 类型之间的位大小不匹配(即，您仍有一些代码块需要更新)。

麻烦制造者似乎是 setFromZ。这里有 Z 指定的整数类型，以及 base::value_type 指定的整数类型。不能保证两者具有相同的位数，因此当发生位不匹配时，该函数中的位移位和位掩码代码无法正常工作。当 uint32_t 是数字类型时(至少在我的环境中)，您的 ideone 代码中出现的该模板的多个实例化发生了不匹配。

编辑:根据标准确认未定义过度右移:引用:SO Post ，请参阅引用标准的已接受答案。

(C++98 §5.8/1) states that: The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.