c - 64 位数学运算，不会丢失任何数据或精度

Question

我相信没有任何适用于 128 位数据的可移植标准数据类型。因此，我的问题是如何使用现有的标准数据类型在不丢失数据的情况下高效地执行 64 位操作。

例如:我有以下两个 uint64_t 类型变量:

uint64_t x = -1; uint64_t y = -1;

现在，如何存储/检索/打印x+y、x-y、x*y 和x/y 等数学运算的结果？

对于上述变量，x+y 的结果为 -1，它实际上是一个带进位 1 的 0xFFFFFFFFFFFFFFFFULL。

void add (uint64_t a, uint64_t b, uint64_t result_high, uint64_t result_low)
{
    result_low = result_high = 0;
    result_low  = a + b;
    result_high += (result_low < a);
}

如何像 add 那样执行其他操作，从而给出正确的最终输出？

如果有人分享处理上溢/下溢等问题的通用算法，我将不胜感激。

任何可能有帮助的标准测试算法。

Answer 1

有很多 BigInteger 库可以处理大数。

1. GMP Library
2. C++ Big Integer Library

如果您想避免库集成并且您的要求非常小，这里是我的基本 BigInteger 片段，我通常将其用于满足基本要求的问题。您可以根据需要创建新方法或重载运算符。 此代码段经过广泛测试且没有错误。

来源

class BigInt {
public:
    // default constructor
    BigInt() {}

    // ~BigInt() {} // avoid overloading default destructor. member-wise destruction is okay

    BigInt( string b ) {
        (*this) = b;    // constructor for string
    }

    // some helpful methods
    size_t size() const { // returns number of digits
        return a.length();
    }
    BigInt inverseSign() { // changes the sign
        sign *= -1;
        return (*this);
    }
    BigInt normalize( int newSign ) { // removes leading 0, fixes sign
        for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- )
            a.erase(a.begin() + i);
        sign = ( a.size() == 1 && a[0] == '0' ) ? 1 : newSign;
        return (*this);
    }

    // assignment operator
    void operator = ( string b ) { // assigns a string to BigInt
        a = b[0] == '-' ? b.substr(1) : b;
        reverse( a.begin(), a.end() );
        this->normalize( b[0] == '-' ? -1 : 1 );
    }

    // conditional operators
    bool operator < (BigInt const& b) const { // less than operator
        if( sign != b.sign ) return sign < b.sign;
        if( a.size() != b.a.size() )
            return sign == 1 ? a.size() < b.a.size() : a.size() > b.a.size();
        for( int i = a.size() - 1; i >= 0; i-- ) if( a[i] != b.a[i] )
                return sign == 1 ? a[i] < b.a[i] : a[i] > b.a[i];
        return false;
    }
    bool operator == ( const BigInt &b ) const { // operator for equality
        return a == b.a && sign == b.sign;
    }



    // mathematical operators
    BigInt operator + ( BigInt b ) { // addition operator overloading
        if( sign != b.sign ) return (*this) - b.inverseSign();
        BigInt c;
        for(int i = 0, carry = 0; i<a.size() || i<b.size() || carry; i++ ) {
            carry+=(i<a.size() ? a[i]-48 : 0)+(i<b.a.size() ? b.a[i]-48 : 0);
            c.a += (carry % 10 + 48);
            carry /= 10;
        }
        return c.normalize(sign);
    }
    BigInt operator - ( BigInt b ) { // subtraction operator overloading
        if( sign != b.sign ) return (*this) + b.inverseSign();
        int s = sign;
        sign = b.sign = 1;
        if( (*this) < b ) return ((b - (*this)).inverseSign()).normalize(-s);
        BigInt c;
        for( int i = 0, borrow = 0; i < a.size(); i++ ) {
            borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
            c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
            borrow = borrow >= 0 ? 0 : 1;
        }
        return c.normalize(s);
    }
    BigInt operator * ( BigInt b ) { // multiplication operator overloading
        BigInt c("0");
        for( int i = 0, k = a[i] - 48; i < a.size(); i++, k = a[i] - 48 ) {
            while(k--) c = c + b; // ith digit is k, so, we add k times
            b.a.insert(b.a.begin(), '0'); // multiplied by 10
        }
        return c.normalize(sign * b.sign);
    }
    BigInt operator / ( BigInt b ) { // division operator overloading
        if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );
        BigInt c("0"), d;
        for( int j = 0; j < a.size(); j++ ) d.a += "0";
        int dSign = sign * b.sign;
        b.sign = 1;
        for( int i = a.size() - 1; i >= 0; i-- ) {
            c.a.insert( c.a.begin(), '0');
            c = c + a.substr( i, 1 );
            while( !( c < b ) ) c = c - b, d.a[i]++;
        }
        return d.normalize(dSign);
    }
    BigInt operator % ( BigInt b ) { // modulo operator overloading
        if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );
        BigInt c("0");
        b.sign = 1;
        for( int i = a.size() - 1; i >= 0; i-- ) {
            c.a.insert( c.a.begin(), '0');
            c = c + a.substr( i, 1 );
            while( !( c < b ) ) c = c - b;
        }
        return c.normalize(sign);
    }

    // << operator overloading
    friend ostream& operator << (ostream&, BigInt const&);

private:
    // representations and structures
    string a; // to store the digits
    int sign; // sign = -1 for negative numbers, sign = 1 otherwise
};

ostream& operator << (ostream& os, BigInt const& obj) {
    if( obj.sign == -1 ) os << "-";
    for( int i = obj.a.size() - 1; i >= 0; i--) {
        os << obj.a[i];
    }
    return os;
}

用法

BigInt a, b, c;
a = BigInt("1233423523546745312464532");
b = BigInt("45624565434216345i657652454352");
c = a + b;
// c = a * b;
// c = b / a;
// c = b - a;
// c = b % a;
cout << c << endl;

// dynamic memory allocation
BigInt *obj = new BigInt("123");
delete obj;