什么是实现整数除法舍入的正确方法? [英] What's the right way to implement integer division-rounding-up?

问题描述

通常需要除以整数，但结果要四舍五入而不是向下取整.一段时间以来，我一直在使用以下函数作为该小型惯用语:

It's very common to need to divide integers but get the result rounded up rather than down. For a while now, I've been using the following function for that mini-idiom:

template <typename S, typename T>
constexpr inline S div_rounding_up(const S& dividend, const T& divisor) 
{
    return (dividend + divisor - 1) / divisor;
}

(至少)存在以下缺陷或可能被视为缺陷:

This has (at least) the following deficiences, or what may be seen as deficiencies:

• 虽然它可以对负操作数按承诺"运行-被称为 div_rounding_up -由于 x/y 表示负 x 和正 y 均四舍五入为零.换句话说，也许我应该实现的是 div_rounding_away_from_zero ，它可以与求反运算交换:，y);} ，我们将得到 f(-x)== -f(x).
• S 域的末尾附近的溢出.
• 当 sizeof(S)>时，行为可能很怪异sizeof(T).
• 长函数名...

• While it works "as promised" with negative operands - it's called div_rounding_up - it would probably make more sense to have this kind of function round away-from-zero, since x / y for negative x and positive y rounds towards zero. In other words, maybe what I should be implementing is div_rounding_away_from_zero, which would be commutative with inversion: Letting auto f = [&y](const S& x) { return div_rounding_away_from_zero(x,y); } we would have f(-x) == -f(x).
• Overflow near the end of the domain of S.
• Possibly weird behavior when sizeof(S) > sizeof(T).
• long function name...

尽管您可以轻松地想出解决这些问题的方法，但是它们又导致了其他可能的缺陷，例如代码中的条件或依赖于计算模数，这可能是昂贵的.

While you can easily think of ways of addressing each of these, they then result in other possible deficiencies, like conditionals in the code, or a reliance on calculating the modulus which may be expensive.

那么有没有正确的方法"来实现这一目标?正确"是指在语义上令人愉悦，高效，避免了上述许多缺陷，并有望得到广泛使用.

So is there a "right way" to implement this? By "right" I mean semantically pleasing, efficient, avoiding as many of the deficiencies above, and hopefully widely-used.

注释:

• 如果您认为应严格限制该函数仅适用于非负参数，请这样说.恕我直言，这有点问题，因为我们不想将类型限制为无符号，并且我们不想检查操作数的符号.似乎我会使用某个联系人作为联系人-C ++还没有联系人.
• 在这里使用 std :: div 和变体是个好主意吗?
• 性能比可读性更重要.最糟糕的情况是可以添加评论.
• 代码不应该是特定于单体系结构的(但是如果您想对不同的体系结构进行ifdef-else，那么请成为我的客人).
• 代码不应采用特定的编译器.

推荐答案

当 sizeof(S)>sizeof(T).

最好使用单个类型参数，并让用户处理所需的转换.这是标准库数学函数使用的方法.

It would probably be better to use a single type argument, and let the user deal with the conversion that they want. This is the approach used by the standard library math functions.

S域末尾附近的溢出.

Overflow near the end of the domain of S.

基于余数的舍入不存在此问题.

A remainder based rounding does not have this problem.

依赖于计算模量，这可能是昂贵的.

reliance on calculating the modulus which may be expensive.

您已经在计算除法，这很昂贵.至少在x86上，除法指令将余数存储在寄存器中，并且 std :: div 的正确实现将使用它.现代编译器甚至还可以优化除法和余数运算的显式使用.

You are already calculating a division, which is expensive. On x86 at least, the division instruction stores the remainder in a register, and a decent implementation of std::div will use it. A modern compiler will even be able to optimize explicit use of division and remainder operation as well.

在这里使用 std :: div 和变体是个好主意吗?

好的.

如果您认为应严格限制该函数仅适用于非负参数，请这样说.

If you think the function should be strictly constained to only work with non-negative arguments, say so.

我认为您至少应该要求参数必须具有相同的符号.除法运算符和余数运算符的舍入方向(自C ++ 11起也通过扩展名 std :: div )进行了实现.有了这个要求，由于没有支持的结果是负数，因此从零舍入到四舍五入之间没有区别.

I think you should at least require that arguments must have the same sign. The direction of rounding of both division and remainder operator (also by extension std::div since C++11) is implementation defined. With this requirement, there is no difference between rounding away from zero, and rounding up, since no supported result is negative.

template <typename T> // single type argument
constexpr T           // constexpr implies inline
div_round_up
(const T& dividend, const T& divisor) 
{
    // no overflows, only 1 expensive operation
    std::div_t dv = std::div(dividend, divisor);
    return dv.quot + (!!dv.rem);
}

这篇关于什么是实现整数除法舍入的正确方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！