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

我将使用 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;
}

生成的代码正是您所期望的(x86-64 上的 gcc 8.3 通过 godbolt ):

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