如何计算整数除法，264 / n？假设：
unsigned long是64位如果我们做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周期）或更清洁（编码）的实现？
phuclv使用-n的想法很聪明，但可以做得更简单。作为无符号长整数，我们有-n = 264-n，然后（-n）/ n = 264 / 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
我想出了另一种灵感来自this question的解决方案。从那里我们知道
（A + + E + A + + +）/ n =
（a1 / n + a2 / n + a3 / n + ... + an / n）+（a1％n + a2％n + a3％n + + +％n）/ n
通过选择a1 = a2 = a3 = ... = an-1 = 1和an = 264 - n，我们将拥有
（1 + + + + + + +）+ / n =（1 + 1 + 1 + ... +（264 - n））/ n = 264 / n
= [（n - 1）* 1 / n +（264 - n）/ n] + [（n - 1）* 0 +（264 - n）％n] / n
=（264-n）/ n +（（264-n）％n）/ n
264 - 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编译器上，long double也具有64位精度，因此您可以使用其中任何一种
(uint64_t)(powl(2, 64)/n)
(uint64_t)(((long double)~0ULL + 1)/n)
(uint64_t)(18446744073709551616.0L/n)
虽然表现可能会更差。这也可以应用于long double具有超过63位有效数字的任何实现，如PowerPC或Sparc
有一个相关的问题关于计算((UINT_MAX + 1)/x)*x - 1：Integer arithmetic: Add 1 to UINT_MAX and divide by n without overflow也有聪明的解决方案。基于我们的基础
264 / n =（264 - n + n）/ n =（264 - n）/ n + 1 =（ - n）/ n + 1
这基本上只是获得Nate Eldredge's answer的另一种方式
这是godbolt上其他编译器的一些演示
也可以看看：
我们使用64位CPU
哪个64位CPU？
通常，如果将带有N位的数字乘以另一个具有M位的数字，则结果将具有最多N + M位。对于整数除法，它是相似的 - 如果具有N位的数字除以具有M位的数字，则结果将具有N-M + 1位。
因为乘法自然是“加宽”（结果的数字比任何一个源数字都多），整数除法自然是“缩小”（结果数字较少）;一些CPU支持“扩大乘法”和“缩小分割”。
换句话说，某些64位CPU支持将128位数字除以64位数字以获得64位结果。例如，在80x86上，它是单个DIV指令。
不幸的是，C不支持“扩大乘法”或“缩小除法”。它只支持“结果与源操作数相同的大小”。
具有讽刺意味的是（对于64位80x86上的无符号64位除数），没有其他选择，编译器必须使用DIV指令将128位数除以64位数。这意味着C语言强制您使用64位分子，然后编译器生成的代码将64位分子扩展为128位，并将其除以64位数以获得64位结果;然后你编写额外的代码来解决语言阻止你使用128位分子开始的事实。
希望您能看到这种情况如何被视为“不太理想”。
我想要的是一种欺骗编译器支持“缩小分区”的方法。例如，可能通过滥用强制转换并希望优化器足够聪明，如下所示：
__uint128_t numerator = (__uint128_t)1 << 64;
if(n > 1) {
return (uint64_t)(numerator/n);
}
我测试了最新版本的GCC，CLANG和ICC（使用https://godbolt.org/）并发现（对于64位80x86）没有一个编译器足够聪明地认识到只需要一个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
你的方式非常好。写它可能会更好：
return 18446744073709551615ul / n + ((n&(n-1)) ? 0:1);
希望是确保编译器注意到它可以执行条件移动而不是分支。
编译和反汇编。