给定整数值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类型的类型转换。有没有一种更直接的方法可以避免额外的乘法(或二次除法)和分支,同时也避免将类型转换为浮点数?


当前回答

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

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

我将y/y化简为1,消除了x + y - 1项,并消除了溢出的可能性。

当x是无符号类型且包含0时,我避免x - 1自动换行。

对于有符号的x,负和零仍然合并为一种情况。

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

其他回答

这适用于正数或负数:

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

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

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

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

我的解决方案是:

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

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

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

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

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

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

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

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

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

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

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

我将y/y化简为1,消除了x + y - 1项,并消除了溢出的可能性。

当x是无符号类型且包含0时,我避免x - 1自动换行。

对于有符号的x,负和零仍然合并为一种情况。

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

您可以使用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;
}