C 中 x64 的 128 位算术

Question

在 x86 上实现 bignum 时，显然数字大小最有效的选择是 32 位。但是，您需要进行最多两倍数字大小的算术运算（即 32+32=33、32*32=64、64/32=32）。幸运的是，x86 不仅提供了这一点，而且还可以通过可移植 C (uint64_t) 访问它。

同样，在 x64 上，最好使用 64 位数字。这将需要 128 位算术（即 64+64=65、64*64=128、128/64=64）。幸运的是，x64 提供了这一点。不幸的是，它不能从可移植的 C 语言访问，尽管显然人们可以深入了解汇编。

所以我的问题是它是否可以从不可移植的 C 访问。x64 上的任何 C 编译器是否提供对此的访问，如果是，语法是什么？

（请注意，我不是在谈论严格视为 32 或 64 位字的集合且它们之间没有进位传播的 128 位向量，而是在谈论实际的 128 位整数运算。）

Answer 1

GCC 4.1 通过 __int128_t 和 __uint128_t 内置类型引入了初始 128 位整数支持，但 128 位类型自 GCC 4.6 为 __int128 / unsigned __int128

Clang 也支持这些类型，尽管我不知道从什么时候开始。 但 Godbolt (3.0.0) 上的第一个版本确实支持 __int128_t

尽管ICC 获得了支持， 自版本 13.0.0 以来支持相同：128 位整数在英特尔 C 编译器中支持 +、-、*、/ 和 %？

另请参阅

• gcc 中是否有 128 位整数？
• 哪些 gcc 版本支持 __int128 内在类型？

---

如果您使用的是 MSVC，则不直接支持 128 位类型，但有许多内在函数可以帮助您执行 128 位类型操作：

• 64*64→128：<代码>_mul128()，_umul128()，__mulh()，__umulh()

• 128/64→64：_div128()，_udiv128()

• 64+64→65：通过将和的低位部分与任意操作数进行比较，可以轻松获得加法中的进位：

  struct uint128 {
      uint64_t H、L；
  };
  
  内联 uint128 add(uint128 a, uint128 b)
  {
      uint128 c；
      cL = aL + bL； // 添加低部分
      cH=aH+bH+(cL＜aL)； // 添加高位部分并进位
      返回c；
  }
  

• 64-64→65：我们可以使用与加法​​中相同的减法方法< /p>

  内联 uint128 sub(uint128 a, uint128 b)
  {
      uint128 c；
      cL = aL - bL；
      cH＝aH-bH-(cL＞aL)；
      返回c；
  }
  

还有一些用于移位的内在函数，尽管实现这些是微不足道的：__shiftleft128()，__shiftright128()

---

如果您使用的是不受支持的编译器，则只需使用一些固定宽度类型从许多可用的库中，这会快得多。例如 ttmath:UInt<4> （128 位 int 类型，四个 32 位肢体），或 Boost.Multi precision 和 calccrypto/uint128_t。像 GMP 这样的任意精度算术库对此来说成本太高。一个例子：优化故事：从 GMP 切换到 gcc 的 __int128 减少了运行时间95%

Answer 2

您可能需要检查 GNU 多精度算术库：

http://gmplib.org/