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

Question

我相信128位数据没有任何便携式标准数据类型.因此,我的问题是如何在不使用现有标准数据类型丢失数据的情况下有效地执行64位操作.

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

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

现在,如何x+y, x-y, x*y and 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图书馆
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;