获取uint64在乘以uint64 * uint64时超过其限制的次数

Question

在将uint64_t与uint64_t相乘时，我需要完成溢出量。这可以通过下面的公式来计算，但是我不能访问128位整数。

使用uint128_t的伪码示例

uint64_t x = ...
uint64_t y = ...
uint128_t result = (uint128_t)x * (uint128_t)y / ((uint128_t)1 << 64);

此外，它还可以通过将uint128_t拆分为[uint64_t, uint64_t]并从示例执行计算来实现。我考虑不使用它，因为我担心它很慢。

Answer 1

英特尔64位架构有一个指令，将两个64位数相乘，结果为128位.要访问它，您有_mulx_u64 intrinsic。

在乘法之后，您只需要得到高64位的部分作为您的result，并丢弃低部分。

Answer 2

首先，我要说，没有可移植的方法来做到这一点，因为在int128_t标准或更低的版本中没有C++20。

考虑到这一点，在Windows中，您可以通过使用MultiplyExtract128函数来实现这一点。使用64作为shift参数除以2^64。