C - 64位的数学运算没有任何数据或精度的损失

Question

我相信没有任何可移植的128位数据的标准数据类型。所以，我的问题是，使用现有的标准数据类型，如何有效地执行64位操作而不丢失数据。

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

uint64_t = -1;

现在，如何存储/检索/打印数学运算的结果，如x+y, x-y, x*y and x/y ?

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

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库/gh>
2. c++大整数库

如果您想避免库集成，并且您的需求非常小，这里是我的基本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;

Answer 2

如果您没有uint128_t，您可以模拟它:

typedef struct uint128_t { uint64_t lo, hi } uint128_t;
...
uint128_t add (uint64_t a, uint64_t b) {
    uint128_t r; r.lo = a + b; r.hi = + (r.lo < a); return r; }
uint128_t sub (uint64_t a, uint64_t b) {
    uint128_t r; r.lo = a - b; r.hi = - (r.lo > a); return r; }

没有内置编译器或汇编器支持的

乘法更难正确处理。从本质上讲，您需要将两个乘数拆分为hi:lo无符号32位，并执行'长乘法'，以处理部分64位乘积之间的进位和'列'。

除法取模返回64位参数的64位结果-所以这不是一个问题，因为你已经定义了这个问题。128位除以64位或128位的操作数是更复杂的操作，需要规范化等。

GMP中longlong.h例程umul_ppmm和udiv_qrnnd给出了多精密/肢体操作的"基本"步骤。

Answer 3

在大多数现代GCC编译器中都支持__int128类型，它可以保存128位整数。

,

__int128 add(__int128 a, __int128 b){
    return a + b;
}