分子除法 2^64

Question

如何在不使用 unit128 的情况下将常数 2^64（即 ULLONG_MAX + 1）除以大于 2 的 uint64？

换句话说，给定x比如2 <= x <= 2^64-1，如何得到商2^64 / x，只用uint64?

问题是我无法表示 2^64，更不用说除法了，所以我希望有一个技巧可以模拟结果。

Answer 1

取ULLONG_MAX / denom，如果denom是2的幂，则加1。在伪代码中：

if (denom == 0) {
    throw ZeroDivisionException;
} else if (denom == 1) {
    throw OverflowException;
} else {
    return ULLONG_MAX / denom + (denom & (denom-1) == 0);
}

或者，奇数denom取ULLONG_MAX / denom，偶数denom取2^63 / (denom / 2):

if (denom == 0) {
    throw ZeroDivisionException;
} else if (denom == 1) {
    throw OverflowException;
} else if (denom & 1) {
    return ULLONG_MAX / denom;
} else {
    return (1ULL << 63) / (denom >> 1);
}

Answer 2

How to to divide the constant 2^64 (i.e. ULLONG_MAX + 1) by uint64 larger than 2

a/b --> (a-b)/b + 1

先从(max _value + 1)中减去x，然后除以x，加1。

// C solution:
uint64_t foo(uint64_t x) {
  return (0u - x)/x + 1; // max_value + 1 is 0 and unsigned subtraction wraps around.
}

当然不能除以0。代码适用于 x >= 2，但不适用于 x == 1，因为商也不可表示。

分子除法 2^64

Division with numerator 2^64

math

division

integer-division

integer-arithmetic