如何在C语言中计算2⁶⁴/n？
如何在C语言中计算2⁶⁴/n？
如何计算整数除法，264/n？假设：
unsigned long是64位的- 我们使用64位的CPU
- 1 < n < 264
如果我们执行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周期）或更简洁（编码）的实现方式？
问题的出现原因是需要计算2的64次方除以n的结果，并且需要使用C语言来实现。下面的解决方法给出了一个函数divide_two_to_the_64，用于计算该结果。
#includeuint64_t divide_two_to_the_64(uint64_t n) { return (-n)/n + 1; }
这个函数的实现非常简单，先将n取负，然后除以n，并加上1。生成的代码如下：
mov rax, rdi
xor edx, edx
neg rax
div rdi
add rax, 1
ret
这段代码使用了gcc 8.3在x86-64平台上的汇编指令。
经过测试，这个函数对于大多数数值都能够正确计算结果。然而，由于测试所有的int64_t值需要很长时间，所以可以先测试32位版本的函数，并检查它是否适用于一些64位值。
另外，建议使用标准的uint64_t类型而不是unsigned long类型，因为unsigned long类型在64位编译器上不一定是64位的。
从这段内容中，我们可以整理出以下问题的出现原因和解决方法：
问题：如何在C语言中计算2⁶⁴/n？
出现原因：该问题的解决方法可以通过参考其他相关问题的解决方案来得到灵感。
解决方法：
1. 根据一个相关问题的解答，我们得知 (a₁ + a₂ + a₃ + ... + aₙ)/n = (a₁/n + a₂/n + a₃/n + ... + aₙ/n) + (a₁ % n + a₂ % n + a₃ % n + ... + aₙ % n)/n。根据这个公式，当选择 a₁ = a₂ = a₃ = ... = aₙ₋₁ = 1 和 aₙ = 2⁶⁴ - 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
根据这个等式，我们可以通过下面的代码来实现计算：
uint64_t twoPow64div(uint64_t n)
{
return (-n)/n + (n + (-n) % n)/n + (n > 1ULL << 63);
}
2. 最后一部分是对结果进行修正，因为我们使用的是无符号整数而不是有符号整数。在MSVC中，可以使用内置函数_udiv128来实现128位除法，代码如下：
uint64_t remainder;
return _udiv128(1, 0, n, &remainder);
3. 对于大多数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的double-double实现。
4. 还有一个相关问题是计算((UINT_MAX + 1)/x)*x - 1的问题，可以通过下面的等式来解决2⁶⁴/n的计算：
2⁶⁴/n = (2⁶⁴ - n + n)/n = (2⁶⁴ - n)/n + 1 = (-n)/n + 1。
以上就是问题的出现原因以及解决方法的整理。
如何在C中计算2⁶⁴/n？
问题的出现原因：
- 一些64位的CPU支持将一个128位的数除以一个64位的数来得到一个64位的结果。
- 然而，C语言不支持“扩展乘法”或“收缩除法”，它只支持“结果与源操作数大小相同”。
解决方法：
- 为了绕过C语言的限制，可以使用内联汇编来实现“收缩除法”。
- 下面是一个例子：
__uint128_t numerator = (__uint128_t)1 << 64;
if (n > 1) {
return (uint64_t)(numerator/n);
}
- 然而，最新版本的GCC、CLANG和ICC编译器并不能智能地将此操作转化为单个DIV指令，它们生成的代码需要调用一个昂贵的函数来获取128位的结果。
- 所以，为了得到理想的代码（只使用DIV指令），需要使用内联汇编。
最佳代码示例（不使用内联汇编）：
mov rax, rdi
xor edx, edx
neg rax
div rdi
add rax, 1
ret
最佳代码示例（使用内联汇编）：
mov edx, 1
xor rax, rax
div rdi
ret
此外，当前的编译器还不能将对`__(u)int128_t`类型的常数除法转化为乘法运算，而是调用了除法函数。同时，应该使用`xor eax, eax`而不是`xor rax, rax`。
需要注意的是，使用最佳代码示例时，如果`n=1`，将会触发除以0的异常，而其他建议都会返回0。