使用int128數據類型進行高精度計算的方法

一、什麼是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表示兩個數的位數之和。使用這種方式實現高精度計算，不需要擔心溢出的問題，而且比使用數組實現要簡單一些。但是，對於除法和取模運算，就需要使用其它的演算法實現了。