时间戳

首页 > 解决方案 > 如何在 C 中计算 2⁶⁴/n？

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

问题描述

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

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

#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 周期）或更清洁（编码）的实现？

标签： cinteger-division

解决方案

我将uint64_t在此处使用（需要<stdint.h>包含），以免您假设unsigned long.

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

uint64_t divide_two_to_the_64(uint64_t 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

推荐阅读