uint64_t：四舍五入的除法-解网

问：

我正在尝试创建一个代码，该代码将 a 除以另一个，并且它对结果应用舍入。代码应该尽可能快，并且适用于所有输入（例如，我希望它现在有条件）。uint64_tuint64_t

我目前的解决方案如下所示：

static inline uint64_t divide_with_rounding(uint64_t n, uint64_t d)
{
    uint64_t a = n / d;
    uint64_t r = n % d;
    return a + (r >= d - (d / 2));
}

GCC 很好地优化了除法+模，并且 .但我想知道是否有更短更好的解决方案。/ 2

例如，像这样的东西：

static inline uint64_t divide_with_rounding(uint64_t n, uint64_t d)
{
    return (n + d / 2) / d;
}

但是，该缺点产生 0.divide_with_rounding(UINT64_MAX, 1000)

c GCC 舍入除整数除法

评论

0赞 phuclv 7/20/2023

这回答了你的问题吗？四舍五入整数除法（而不是截断）

1赞 phuclv 7/20/2023

四舍五入到最接近：，到+inf：。重复：实现整数除法舍入的正确方法是什么？，在 C++ 中用下限、ceil 和向外舍入模式除整整，在 C 中用舍入进行有符号整数除法，在 C / C++ 中实现整数除法的快速上限(n + d/2)/d(n + d - 1)/d

答：

2赞 phuclv 7/20/2023 #1

表达式在数学上是 round（x/d） = ⌊（x + d/2）/d⌋。根据楼层函数的性质 ⌊x + n⌋ = ⌊x⌋ + n，我们可以证明，在 d 的情况下，结果是

$\left\lfloor \frac{n + \left\lfloor \frac{d}{2}\right\rfloor }{d} \right\rfloor = \left\lfloor \frac{n - \frac{d}{2} + d}{d} \right\rfloor = \left\lfloor \frac{n - \frac{d}{2}}{d} + 1 \right\rfloor = \left\lfloor \frac{n - \frac{d}{2}}{d} \right\rfloor + 1$

如果 d 是奇数，我们可以替换 d = 2k + 1 并证明结果是相同的。因此，您可以只使用

if (n >= d/2)
    return (n - d/2)/d + 1;
else
    return (n + d/2)/d;

这样可以避免溢出的情况n + d/2

但是，如果不是编译时常量，那么如果分支错误预测成本很高，则执行 128 x 64 位除法可能会更快。在 MSVC 中，您可以这样做d

uint64_t nH = 0, nL = n, rem = 0;
nL += d/2;
nH += nL < n;                        // { nH, nL } += d/2
return _udiv128(nH, nL, d, &rem);    // { nH, nL } / d

在具有 GCC、ICC、Clang 等类型的编译器中......直接使用即可__int128

__int128 N = n;
N += d/2;
return N/d;

上一个：Python floor division 中的舍入错误

下一个：ImportError：无法从“torchvision.models.vgg”导入名称“model_urls”