c - C 中 x64 上的 128 位算术

Question

在 x86 上实现 bignums 时，显然最有效的数字大小选择是 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 编译器是否提供对此的访问，如果是，语法是什么？

(请注意，我说的不是 128 位 vector ，它们被严格视为 32 位或 64 位字的集合，它们之间没有进位传播，而是实际的 128 位整数运算。)

Answer 1

GCC 4.1 引入了初始的 128 位整数支持 __int128_t和 __uint128_t内置类型，但 128 位类型自 GCC 4.6 后正式发布作为 __int128 / unsigned __int128

Clang 也支持这些类型，虽然我不知道从什么时候开始。第一个版本在 Godbolt (3.0.0) 支持 __int128_t虽然

ICC 自版本 13.0.0 以来获得了相同的支持:128-bit integers supporting +, -, *, /, and % in the Intel C Compiler?

另见

• Is there a 128 bit integer in gcc?
• What gcc versions support the __int128 intrinsic type?

---

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

• 64*64=128: _mul128() , _umul128() , __mulh() , __umulh()

• 128/64=64: _div128() , _udiv128()

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

  struct uint128 {
      uint64_t H, L;
  };
  
  inline uint128 add(uint128 a, uint128 b)
  {
      uint128 c;
      c.L = a.L + b.L;                // add low parts
      c.H = a.H + b.H + (c.L < a.L);  // add high parts and carry
      return c;
  }
  

  128位减法可以用同样的东西

虽然实现这些很简单，但也有用于移位的内在函数: __shiftleft128() , __shiftright128()

---

如果您使用的是不受支持的编译器，那么只需使用许多可用库中的一些固定宽度类型，这样会快得多。例如 ttmath:UInt<4> (具有四个 32 位分支的 128 位 int 类型)，或 (u)int128_t在 Boost.Multiprecision和 calccrypto/uint128_t .像 GMP 这样的任意精度算术库对此来说成本太高了。一个例子:Optimization story: Switching from GMP to gcc's __int128 reduced run time by 95%