实现整数除法向上舍入的正确方法是什么?



通常需要对整数进行除法,但结果是向上取整而不是向下取整。一段时间以来,我一直在为这个小习惯用法使用以下函数:

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

这(至少)有以下缺陷,或者可以被视为缺陷:

  • 虽然它对负操作数"如约"工作——它被称为div_rounding_up——但让这种函数从零开始舍入可能更有意义,因为负x和正yx / y向零舍入。换句话说,也许我应该实现的是div_rounding_away_from_zero,它可以与反转交换:让auto f = [&y](const S& x) { return div_rounding_away_from_zero(x,y); }成为f(-x) == -f(x)
  • S的域末尾附近溢出
  • sizeof(S) > sizeof(T)
  • 长函数名

虽然你可以很容易地想出解决每一个问题的方法,但它们会导致其他可能的缺陷,比如代码中的条件,或者依赖于计算可能很昂贵的模数。

那么,有没有"正确的方法"来实现这一点呢?我所说的"正确"是指语义上令人愉快、高效、避免了上述许多不足,并有望广泛使用。

注意:

  • 如果你认为函数应该严格保持为只使用非负参数,那就这么说吧。IMHO会有点问题,因为我们不想约束类型为无符号,也不想检查操作数的符号。这似乎是我想使用联系人的东西——而C++还没有
  • 在这里使用std::div和变体是个好主意吗
  • 性能比可读性更重要。最坏的情况是可以添加评论
  • 代码不应该是特定于单个体系结构的(但如果您想为不同的体系结构定义else,那么请接受我的邀请)
  • 代码不应采用特定的编译器

sizeof(S) > sizeof(T)时可能出现异常行为。

最好使用单个类型参数,并让用户处理他们想要的转换。这是标准库数学函数所使用的方法。

在S.的域末尾附近溢出

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

依赖于计算模量,这可能是昂贵的。

您已经在计算除法了,这很昂贵。至少在x86上,除法指令将余数存储在寄存器中,std::div的良好实现将使用它。现代编译器甚至能够优化除法和余数运算的显式使用。

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

当然。

如果你认为函数应该严格保持为只使用非负参数,那么就这么说吧。

我认为您至少应该要求参数必须具有相同的符号。除法和余数运算符(自C++11以来也扩展为std::div)的舍入方向是实现定义的。有了这个要求,从零取整和向上取整之间没有区别,因为没有支持的结果是负的。

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);
}

相关内容

  • 没有找到相关文章

最新更新