一、什么是int128数据类型
在C++中,int是用来表示整数的数据类型,int类型占用4个字节(32位),最多能够表示2的31次方-1(即2147483647)。如果需要进行更大的整数计算,可以使用long long类型,其占用8个字节(64位),最多能够表示2的63次方-1(即9223372036854775807)。但是,这依然不能满足高精度计算的需要。
int128数据类型是在uint128_t(128位无符号整数)的基础上,进行了带符号的扩展(signed extension)得到的数据类型。它占用16个字节(128位),最多能够表示2的127次方-1(即170141183460469231731687303715884105727)的整数范围,可以支持高精度计算。
signed __int128 a = 123456789101112131415; // 定义一个int128类型整数变量 std::cout << a << std::endl; // 输出:123456789101112131415
二、int128类型的运算
与普通整数类型相比,int128类型也支持加减乘除等基本运算操作,只需要使用对应的运算符即可。
对于复杂的高精度计算,可以使用字符串读入整数,然后将字符串转换为int128类型进行计算。计算结果再转换为字符串进行输出,这样既保证了计算精确度,又避免了溢出的问题。
// 将字符串转换为int128类型 signed __int128 str2int128(std::string str) { signed __int128 x = 0; for (auto c : str) { if (isdigit(c)) { x = x * 10 + (c - '0'); } } return x; } // 将int128类型转换为字符串 std::string int1282str(signed __int128 x) { std::string str; if (x < 0) { str += "-"; x = -x; } while (x) { str += static_cast('0' + x % 10); x /= 10; } if (str.empty()) { str = "0"; } else if (str.front() == '-') { std::reverse(str.begin() + 1, str.end()); } else { std::reverse(str.begin(), str.end()); } return str; } signed __int128 a = str2int128("123456789101112131415"); signed __int128 b = str2int128("987654321012345678901"); signed __int128 c = a * b; std::cout << int1282str(c) << std::endl; // 输出:1219326311370217951467806858647467256758347028815277915
三、使用int128类型实现高精度计算
下面提供一个使用int128类型实现高精度计算加法和乘法的示例程序。
Addition
std::string int128_add(std::string str1, std::string str2) { signed __int128 x = str2int128(str1); signed __int128 y = str2int128(str2); return int1282str(x + y); }
Multiplication
std::string int128_mul(std::string str1, std::string str2) { signed __int128 x = str2int128(str1); signed __int128 y = str2int128(str2); signed __int128 z = x * y; return int1282str(z); }
使用int128类型进行加法和乘法计算,其时间复杂度都是O(n),其中n表示两个数的位数之和。使用这种方式实现高精度计算,不需要担心溢出的问题,而且比使用数组实现要简单一些。但是,对于除法和取模运算,就需要使用其它的算法实现了。