使用int128数据类型进行高精度计算的方法

NCUN • 2024-10-03 23:49 • 编程

一、什么是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表示两个数的位数之和。使用这种方式实现高精度计算，不需要担心溢出的问题，而且比使用数组实现要简单一些。但是，对于除法和取模运算，就需要使用其它的算法实现了。

原创文章，作者：NCUN，如若转载，请注明出处：https://www.506064.com/n/132035.html