C / c++中整数除法的快速上限

给定整数值x和y, C和c++都返回为商q = x/y，即浮点等价物的整层。我感兴趣的是一种返回天花板的方法。例如，ceil(10/5)=2和ceil(11/5)=3。

最明显的方法是:

q = x / y;
if (q * y < x) ++q;

这需要额外的比较和乘法;和我所见过(实际上使用过)的其他方法都涉及到转换为float或double。有没有一种更直接的方法可以避免额外的乘法(或二次除法)和分支，同时也避免将类型转换为浮点数?

217319 次浏览
小开
最佳答案

对于正数，求x除以y的上限q。

unsigned int x, y, q;

把…

q = (x + y - 1) / y;

或(避免x+y溢出)

q = 1 + ((x - 1) / y); // if x != 0
小开

你可以使用cstdlib中的div函数来获得商&余数在单个调用中，然后分别处理天花板，如下所示

#include <cstdlib>
#include <iostream>


int div_ceil(int numerator, int denominator)
{
std::div_t res = std::div(numerator, denominator);
return res.rem ? (res.quot + 1) : res.quot;
}


int main(int, const char**)
{
std::cout << "10 / 5 = " << div_ceil(10, 5) << std::endl;
std::cout << "11 / 5 = " << div_ceil(11, 5) << std::endl;


return 0;
}
小开

Sparky的回答是解决这个问题的一种标准方法，但正如我在评论中所写的，您将面临溢出的风险。这可以通过使用更宽的类型来解决，但如果你想划分__abc0呢?

Nathan Ernst的答案提供了一个解决方案，但它涉及一个函数调用、一个变量声明和一个条件，这使得它并不比OPs代码短，甚至可能更慢，因为它更难优化。

我的解决方案是:

q = (x % y) ? x / y + 1 : x / y;

它将比OPs代码略快，因为取模和除法在处理器上使用相同的指令执行，因为编译器可以看到它们是等效的。至少gcc 4.4.1在x86上使用-O2标志执行此优化。

理论上，编译器可能会在Nathan Ernst的代码中内联函数调用并发出相同的东西，但gcc在我测试时没有这样做。这可能是因为它将编译的代码绑定到标准库的单个版本。

最后需要注意的是，在现代机器上，这些都无关紧要，除非您处于一个非常紧密的循环中，并且所有数据都在寄存器或l1缓存中。否则，所有这些解决方案都一样快，除了Nathan Ernst的，如果函数必须从主存中取出，它可能会明显慢一些。

小开

这个怎么样?(要求y是非负的，所以在y是一个没有非负保证的变量的罕见情况下不要使用这个)

q = (x > 0)? 1 + (x - 1)/y: (x / y);

我将y/y减为1，消除了术语x + y - 1和它带来的任何溢出的机会。

当x是unsigned类型并且包含0时，我避免x - 1自动换行。

对于有符号的x，负和零仍然合并为一个case。

在现代通用CPU上可能没有太大的好处，但在嵌入式系统中，这比其他任何正确答案都要快得多。

小开

对于正数:

    q = x/y + (x % y != 0);
小开

这适用于正数或负数:

q = x / y + ((x % y != 0) ? !((x > 0) ^ (y > 0)) : 0);

如果有余数，则检查x和y是否具有相同的符号，并相应地添加1。

小开

对于正的和负的x都有一个解决方案，但只适用于正的y，只有一个除法，没有分支:

int div_ceil(int x, int y) {
return x / y + (x % y > 0);
}

注意，如果x为正，则除法趋向于零，如果提醒符不为零，则应加1。

如果x为负，则除法趋近于0，这就是我们所需要的，并且我们不会添加任何东西，因为x % y不是正数

小开

简化的通用形式，

int div_up(int n, int d) {
return n / d + (((n < 0) ^ (d > 0)) && (n % d));
} //i.e. +1 iff (not exact int && positive result)

对于更一般的答案，c++函数用于整数除法，具有良好定义的舍入策略

小开

我本想发表评论，但我的知名度不够高。

据我所知，对于正参数和2的幂的除数，这是最快的方法(在CUDA中测试过):

//example y=8
q = (x >> 3) + !!(x & 7);

对于一般的正面论证，我倾向于这样做:

q = x/y + !!(x % y);
小开

使用O3编译，编译器优化性能良好。

q = x / y;
if (x % y)  ++q;
小开

对于有符号整数或无符号整数。

q = x / y + !(((x < 0) != (y < 0)) || !(x % y));

有符号的股利和无符号的因子。

q = x / y + !((x < 0) || !(x % y));

对于无符号股利和有符号因子。

q = x / y + !((y < 0) || !(x % y));

对于无符号整数。

q = x / y + !!(x % y);

零除数失败(与本机操作一样)。不能导致溢出。

对应的地板和模constexpr实现在这里，以及模板来选择必要的重载(作为完全优化和防止不匹配的符号比较警告):

https://github.com/libbitcoin/libbitcoin-system/wiki/Integer-Division-Unraveled


提交答案