如何在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

phuclv的使用想法-n很聪明，但可以简化很多。作为无符号长型，我们有-n = 2 ⁶⁴ -n，然后（-n）/ n = 2 ⁶⁴ / n-1，我们可以简单地加回1。

unsigned long foo(unsigned long n) {
  return (-n)/n + 1;
}

生成的代码正是您所期望的（通过godbolt在x86-64上的gcc 8.3 ）：

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

Answer 2

我提出了另一个受此问题启发的解决方案。从那里我们知道

(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);
}

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

然而，在 MSVC 上有一个128 位除法的内在函数，所以你可以像这样使用

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

这导致最干净的输出

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

这是演示

在大多数 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及其双倍实现

有一个关于计算的相关问题((UINT_MAX + 1)/x)*x - 1： 整数算术：加 1 到 UINT_MAX 并除以 n 而不会溢出，也有聪明的解决方案。基于此，我们有

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

这本质上只是获得Nate Eldredge 答案的另一种方式

这是Godbolt上其他编译器的一些演示

也可以看看：

• 将常数（2 的幂）除以整数的技巧
• 通过快速浮点倒数高效计算 2**64 / 除数