C中x64上的128位算术 [英] 128-bit arithmetic on x64 in C
问题描述
在x86上实现bignums时，显然，数字大小最有效的选择是32位.但是，您需要算术运算，最大数字位数应为两倍(即32 + 32 = 33、32 * 32 = 64、64/32 = 32).幸运的是，x86不仅提供了此功能，还可以从便携式C(uint64_t)对其进行访问.
When implementing bignums on x86, obviously the most efficient choice for digit size is 32 bits. However, you need arithmetic up to twice the digit size (i.e. 32+32=33, 32*32=64, 64/32=32). Fortunately, not only does x86 provide this, but it's also accessible from portable C (uint64_t).
同样，在x64上，最好使用64位数字.这将需要128位算术运算(即64 + 64 = 65、64 * 64 = 128、128/64 = 64).幸运的是，x64提供了此功能.不幸的是，尽管显然有人可以将其插入汇编中，但无法通过便携式C进行访问.
Similarly, on x64 it would be desirable to use 64-bit digits. This would require 128 bit arithmetic (i.e. 64+64=65, 64*64=128, 128/64=64). Fortunately, x64 provides this. Unfortunately, it's not accessible from portable C, though obviously one could dip into assembly.
所以我的问题是，它是否可以从不可移植的C访问.x64上的任何C编译器都提供对此的访问吗，如果可以，语法是什么?
So my question is whether it's accessible from non-portable C. Do any C compilers on x64 provide access to this, and if so, what's the syntax?
(请注意，我并不是在说128位向量被严格地视为32或64位字的集合，它们之间没有进位传播，而是实际的128位整数运算.)
(Note that I'm not talking about 128-bit vectors that are strictly treated as collections of 32 or 64-bit words with no carry propagation between them, but about actual 128-bit integer operations.)
推荐答案
GCC 4.1通过__int128_t和__uint128_t内置类型引入了最初的128位整数支持，但自
GCC 4.1 introduced initial 128-bit integer support with the __int128_t and __uint128_t built-in types but 128-bit type was officially released since GCC 4.6 as __int128 / unsigned __int128
Clang也支持这些类型，尽管我从什么时候开始不知道. Godbolt (3.0.0)上的第一个版本确实支持__int128_t
Clang also supports those types although I don't know since when. The first version on Godbolt (3.0.0) does support __int128_t though
ICC自版本13.0.0起获得了相同的支持: 128位整数支持+，-，*，/和％英特尔C编译器?
ICC gained the same support since version 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位操作:
If you're on MSVC then there's no direct support for a 128-bit type but there are many intrinsics helping you do 128-bit operations:
-
64 * 64 = 128:
_mul128()，_umul128()，__mulh()，__umulh()
128/64 = 64: _div128() ， _udiv128()
128/64=64: _div128(), _udiv128()
64 + 64 = 65:通过将总和的下半部分与任何操作数进行比较，可以轻松获得加法进位:
64+64=65: The carry in an addition can be easily obtained by comparing the low part of the sum with any of the operands:
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位减法
The same thing can be used for 128-bit subtraction
尽管实现这些功能很简单，但也有一些用于移动的内在函数: __shiftright128()
There are also intrinsics for shifting although implementing these is trivial: __shiftleft128(), __shiftright128()
如果您使用的是不受支持的编译器，则只需使用许多可用库中的某些固定宽度类型，这会更快.例如 ttmath:UInt<4> (具有四个32位分支的128位int类型)，或__int128可以将运行时间减少95％
If you're on an unsupported compiler then just use some fixed-width types from many available libraries, that would be much faster. For example ttmath:UInt<4> (a 128-bit int type with four 32-bit limbs), or (u)int128_t in Boost.Multiprecision and calccrypto/uint128_t. An arbitrary-precision arithmetic library like GMP is just too costly for this. One example: Optimization story: Switching from GMP to gcc's __int128 reduced run time by 95%
这篇关于C中x64上的128位算术的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
