如何在 C 中计算 2⁶⁴/n？

Question

如何计算整数除法，2⁶⁴/n？假设：

unsigned long 是 64 位
我们使用 64 位 CPU
1 < n < 2⁶⁴

如果我们做 18446744073709551616ul / n，我们会在编译时得到 warning: integer constant is too large for its type。这是因为我们无法在 64 位 CPU 中表达 2⁶⁴。另一种方式如下：

#define IS_POWER_OF_TWO(x) ((x & (x - 1)) == 0)

unsigned long q = 18446744073709551615ul / n;
if (IS_POWER_OF_TWO(n))
    return q + 1;
else
    return q;

是否有更快（CPU 周期）或更清洁（编码）的实施？

Answer 1

你的方法很不错。这样写可能更好:

return 18446744073709551615ul / n + ((n&(n-1)) ? 0:1);

希望确保编译器注意到它可以执行条件移动而不是分支。

编译反汇编

Answer 2

我想出了另一个解决方案，其灵感来自 this question。从那里我们知道

(a₁ + a₂ + a₃ + ... + a_n)/n =

(a₁/n + a₂/n + a₃/n + ... + a_n/n) + (a₁ % n + a₂ % n + a₃ % n + ... + a_n % n)/n

通过选择a₁ = a₂ = a₃ = ... = a_n-1 = 1 和 a_n = 2⁶⁴ - n 我们将有

(a₁ + a₂ + a₃ + ... + a_n)/n = (1 + 1 + 1 + ... + (2⁶⁴ - n))/n = 2⁶⁴/n

= [(n - 1)*1/n + (2⁶⁴ - n)/n] + [(n - 1)*0 + (2⁶⁴ - n) % n]/n

= (2⁶⁴ - n)/n + ((2⁶⁴ - n) % n)/n

2⁶⁴ - n是n的2的补码，即-n，也可以写成~0 - n + 1。所以最终的解决方案是

uint64_t twoPow64div(uint64_t n)
{
    return (-n)/n + (n + (-n) % n)/n + (n > 1ULL << 63);
}

最后一部分是更正结果，因为我们处理的是无符号整数，而不是像另一个问题中那样处理有符号整数。在我的电脑上检查了 32 位和 64 位版本，结果与您的解决方案匹配

但是在 MSVC 上有一个 intrinsic for 128-bit division，所以你可以这样使用

uint64_t remainder;
return _udiv128(1, 0, n, &remainder);

产生最干净的输出

    mov     edx, 1
    xor     eax, eax
    div     rcx
    ret     0

这是demo

在大多数 x86 编译器上（一个明显的例外是 MSVC）long double 也有 64 位精度，因此您可以使用其中任何一个

(uint64_t)(powl(2, 64)/n)
(uint64_t)(((long double)~0ULL)/n)
(uint64_t)(18446744073709551616.0L/n)

虽然性能可能会更差。这也可以应用于 long double 具有超过 63 位有效数的任何实现，例如 PowerPC with its double-double implementation

有一个关于计算 ((UINT_MAX + 1)/x)*x - 1 的相关问题：也有聪明的解决方案。基于此我们有

2⁶⁴/n = (2⁶⁴ - n + n)/n = (2⁶⁴ - n)/n + 1 = (-n)/n + 1

这本质上只是获得

的另一种方式

这是 godbolt

上其他编译器的一些演示

另请参阅：

Efficient computation of 2**64 / divisor via fast floating-point reciprocal

Answer 3

我将在这里使用 uint64_t（需要包含 <stdint.h>），这样就不需要您对 unsigned long.

大小的假设

phuclv 使用 -n 的想法很聪明，但可以做得更简单。作为无符号 64 位整数，我们有 -n = 2⁶⁴-n，然后 (-n)/n = 2⁶⁴/n - 1，我们可以简单地加回 1。

uint64_t divide_two_to_the_64(uint64_t n) {
  return (-n)/n + 1;
}

生成的代码正是您所期望的（gcc 8.3 on x86-64 via godbolt）：

    mov     rax, rdi
    xor     edx, edx
    neg     rax
    div     rdi
    add     rax, 1
    ret

Answer 4

We use a 64-bit CPU

哪个 64 位CPU？

一般来说，如果将一个 N 位的数字乘以另一个 M 位的数字，结果将有 N+M 位。对于整数除法，它是相似的——如果一个 N 位的数字除以一个 M 位的数字，结果将有 N-M+1 位。

因为乘法自然是"widening"（结果的位数比任一源数都多）而整数除法自然是"narrowing"（结果的位数少）；一些 CPU 支持 "widening multiplication" 和 "narrowing division".

换句话说，一些64位的CPU支持128位的数除以64位的数得到64位的结果。例如，在 80x86 上它是一条 DIV 指令。

遗憾的是，C 不支持 "widening multiplication" 或 "narrowing division"。只支持"result is same size as source operands".

具有讽刺意味的是（对于 64 位 80x86 上的无符号 64 位除数）没有其他选择，编译器必须使用 DIV 指令将 128 位数字除以 64 位数字.这意味着C语言强制你使用64位分子，然后编译器生成的代码将你的64位分子扩展为128位，并除以64位数字得到64位结果；然后您编写额外的代码来解决该语言阻止您使用 128 位分子开头的事实。

希望您能了解如何考虑这种情况"less than ideal"。

我想要的是一种诱使编译器支持 "narrowing division" 的方法。例如，也许通过滥用转换并希望优化器足够聪明，像这样：

  __uint128_t numerator = (__uint128_t)1 << 64;
  if(n > 1) {
      return (uint64_t)(numerator/n);
  }

我针对最新版本的 GCC、CLANG 和 ICC（使用 https://godbolt.org/ ）对此进行了测试，发现（对于 64 位 80x86）none 编译器足够聪明，可以意识到只需要一条 DIV 指令（它们都生成执行 call __udivti3 的代码，这是获得 128 位结果的昂贵函数）。编译器只会在（128 位）分子为 64 位时使用 DIV（并且其前面会有一个 XOR RDX,RDX 以将 128 位分子的最高半部分设置为零）。

换句话说，获得理想代码（64 位 80x86 上的 DIV 指令本身）的唯一方法可能是求助于内联汇编。

例如，没有内联汇编（来自 Nate Eldredge 的回答）的最佳代码将是：

    mov     rax, rdi
    xor     edx, edx
    neg     rax
    div     rdi
    add     rax, 1
    ret

...可能的最佳代码是：

    mov     edx, 1
    xor     rax, rax
    div     rdi
    ret

如何在 C 中计算 2⁶⁴/n？

How to compute 2⁶⁴/n in C?

c

integer-division