64位数学运算，不会丢失任何数据或精度 [英] 64 bit mathematical operations without any loss of data or precision
问题描述
我认为128位数据没有任何可移植的标准数据类型.因此，我的问题是，如何使用现有的标准数据类型有效地执行64位操作而又不会丢失数据.
I believe there isn't any portable standard data type for 128 bits of data. So, my question is about how efficiently 64 bit operations can be carried out without loss of data using existing standard data-types.
例如:我有以下两个uint64_t类型变量:
For example : I have following two uint64_t type variables:
uint64_t x = -1; uint64_t y = -1;
uint64_t x = -1; uint64_t y = -1;
现在，如何存储/检索/打印诸如x+y, x-y, x*y and x/y之类的数学运算的结果?
Now, how the result of mathematical operations such as x+y, x-y, x*y and x/y can be stored/retrieved/printed ?
对于上述变量，x + y的值为-1，实际上是带有进位1的0xFFFFFFFFFFFFFFFFULL.
For above variables, x+y results in value of -1 which is actually a 0xFFFFFFFFFFFFFFFFULL with a carry 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一样执行其他操作，从而给出适当的最终输出?
How other operations can be performed as like add, which gives proper final output ?
如果有人使用通用算法来处理此类操作可能引起的上溢/下溢等情况，我将不胜感激.
I'd appreciate if someone share the generic algorithm which take care of overflow/underflow etcetera that might comes into picture using such operations.
任何经过标准测试的算法都可以提供帮助.
Any standard tested algorithms which might can help.
推荐答案
有很多BigInteger库可以处理大数.
There are lot of BigInteger libraries out there to manipulate big numbers.
- GMP Library
- C++ Big Integer Library
如果要避免库集成并且您的需求很小，这是我通常用于解决基本需求问题的基本BigInteger代码段.您可以根据需要创建新方法或重载运算符. 此代码段经过了广泛的测试并且没有错误.
If you want to avoid library integration and your requirement is quite small, here is my basic BigInteger snippet that I generally use for problem with basic requirement. You can create new methods or overload operators according your need. This snippet is widely tested and bug free.
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;
这篇关于64位数学运算，不会丢失任何数据或精度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
