没有溢出的无符号整数的舍入

Question

我正在寻找一种溢出安全的方法来执行无符号整数的舍入。

我有这个：

uint roundDiv(uint n, uint d)
{
    return (n + d / 2) / d;
}

但不幸的是，表达式 n + d / 2 可能会溢出。

我想我必须检查 n % d 是否小于 d / 2。

但 d / 2 本身可能会截断（当 d 为奇数时）。

所以我想我应该检查 n % d * 2 是否小于 d。

或者即使没有逻辑条件，也依赖于 n % d * 2 / d 是 0 或 1 的事实：

uint roundDiv(uint n, uint d)
{
    return n / d + n % d * 2 / d;
}

这很好用，但是，n % d * 2 可能会再次溢出。

是否有任何自定义方法来实现溢出安全的整数除法？

更新

我想到了这个：

uint roundDiv(uint n, uint d)
{
    if (n % d < (d + d % 2) / 2)
        return n / d;
    return n / d + 1;
}

不过，表达式 d + d % 2 可能会溢出。

Answer 1

如 OP 所述，在任何阶段避免溢出的方法是将余数与除数的一半进行比较，但结果并不像乍看起来那么明显。这里有一些例子，假设 0.5 会四舍五入。首先是奇数：

Numerator   Divisor Required    Quotient    Remainder   Half divisor    Quot < Req?
3           3       1           1           0           1               no
4           3       1           1           1           1               no
5           3       2           1           2           1               yes
6           3       2           2           0           1               no

以上，唯一需要的增量是d / 2 < remainder。现在有了偶数：

Numerator   Divisor Required    Quotient    Remainder   Half divisor    Quot < Req?
4           4       1           1           0           2               no
5           4       1           1           1           2               no
6           4       2           1           2           2               yes
7           4       2           1           3           2               yes
8           4       2           2           0           2               no

但是这里，d / 2 <= remainder时需要自增。

总结：

根据 odd 或 even 除数，您需要不同的条件。

Answer 2

return n/d + (d-d/2 <= n%d);

没有溢出的无符号整数的舍入

Round division of unsigned integers with no overflow

c

rounding

integer-division

更新