64位数学运算,不会丢失任何数据或精度
我相信128位数据没有任何便携式标准数据类型。 因此,我的问题是如何在不使用现有标准数据类型丢失数据的情况下有效地执行64位操作。
例如:我有两个uint64_t类型变量:
uint64_t x = -1; uint64_t y = -1;
现在,如何存储/检索/打印数学运算的结果,如x+y, xy, 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
一样执行其他操作,从而提供适当的最终输出?
如果有人共享通用算法,我会很感激,这些算法可以解决使用这些操作可能出现的溢出/下溢等问题。
任何可能有帮助的标准测试算法。
有很多BigInteger
库来操纵大数字。
- GMP图书馆
- 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() != basize() ) return sign == 1 ? a.size() < basize() : a.size() > basize(); for( int i = a.size() - 1; i >= 0; i-- ) if( a[i] != ba[i] ) return sign == 1 ? a[i] < ba[i] : a[i] > ba[i]; return false; } bool operator == ( const BigInt &b ) const { // operator for equality return a == ba && 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= 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 bainsert(babegin(), '0'); // multiplied by 10 } return c.normalize(sign * b.sign); } BigInt operator / ( BigInt b ) { // division operator overloading if( b.size() == 1 && ba[0] == '0' ) ba[0] /= ( ba[0] - 48 ); BigInt c("0"), d; for( int j = 0; j < a.size(); j++ ) da += "0"; int dSign = sign * b.sign; b.sign = 1; for( int i = a.size() - 1; i >= 0; i-- ) { cainsert( cabegin(), '0'); c = c + a.substr( i, 1 ); while( !( c < b ) ) c = c - b, da[i]++; } return d.normalize(dSign); } BigInt operator % ( BigInt b ) { // modulo operator overloading if( b.size() == 1 && ba[0] == '0' ) ba[0] /= ( ba[0] - 48 ); BigInt c("0"); b.sign = 1; for( int i = a.size() - 1; i >= 0; i-- ) { cainsert( cabegin(), '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;
你可以模仿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位,并执行’long multiplication’处理部分64位乘积之间的进位和’列’。
给定64位参数的除法和模数返回64位结果 – 所以这不是问题,因为您已经定义了问题。 将128位除以64位或128位操作数是一项复杂得多的操作,需要归一化等。
umul_ppmm
udiv_qrnnd
例程umul_ppmm
和udiv_qrnnd
为多精度/肢体操作提供了“基本”步骤。
在大多数现代GCC编译器中,支持__int128
类型,它可以容纳128位整数。
例,
__int128 add(__int128 a, __int128 b){ return a + b; }