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

如何计算整数除法264/n？假设:

unsigned long是64位

我们使用64位CPU

1
如果我们执行18446744073709551616ul / n，我们将在编译时获得warning: integer constant is too large for its type。这是因为我们无法在64位CPU中表示264。另一种方法如下:

#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周期)或更干净的(编码)实现？

最佳答案

我将在此处使用uint64_t(需要包括<stdint.h>)，以便不要求您假设unsigned long的大小。
phuclv使用-n的想法很聪明，但是可以简化很多。作为无符号的64位整数，我们有-n = 264-n，然后(-n)/n = 264/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

关于c - 如何在C中计算2⁶⁴/n？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55565537/