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

Question

给定整数值,x并且yC和C++都返回作为q = x/y浮点等效的底数的商.我对一种返回天花板的方法很感兴趣.例如,ceil(10/5)=2和ceil(11/5)=3.

显而易见的方法包括:

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

这需要额外的比较和乘法; 我见过的其他方法(事实上使用)涉及铸造为float或double.是否有更直接的方法可以避免额外的乘法(或第二个除法)和分支,并且还可以避免作为浮点数进行转换？

Answer 1

围捕......

unsigned int x, y, q;

或(避免x + y溢出)

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

Answer 2

对于正数:

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

Answer 3

Sparky的答案是解决这个问题的一种标准方法,但正如我在评论中写的那样,你冒着溢出的风险.这可以通过使用更宽的类型来解决,但是如果你想分割long longs呢？

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

我的解决方案是:

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

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

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

最后要注意的是,在现代机器上,这一切都不重要,除非您处于非常紧凑的循环中并且所有数据都在寄存器或L1缓存中.否则所有这些解决方案都会同样快,除了可能是Nathan Ernst之外,如果必须从主存储器获取该函数,这可能会明显变慢.

Answer 4

您可以使用divcstdlib中的函数在单个调用中获取商和余数,然后单独处理上限,如下所示

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

Answer 5

这个怎么样？(要求y为非负数,所以在极少数情况下不要使用它,其中y是一个没有非负性保证的变量)

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

我减少y/y到一个,消除了这个术语,x + y - 1并且有任何溢出的可能性.

我避免x - 1在x无符号类型时回绕并且包含零.

对于签名x,负面和零仍然合并为一个案例.

对于现代通用CPU来说可能不是一个巨大的好处,但在嵌入式系统中,这比任何其他正确的答案要快得多.

Answer 6

我宁愿发表评论，但我没有足够高的代表。

据我所知，对于正参数和 2 的幂的除数，这是最快的方法（在 CUDA 中测试）：

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

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

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

Answer 7

有正面和负面的解决方案,x但只有y1个分区和没有分支的正面解决方案:

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

注意,如果x是正数则则除数为零,如果提醒不为零,我们应该加1.

如果x是负数则则除数为零,这就是我们需要的,我们不会添加任何东西,因为x % y它不是正数

Answer 8

这适用于正数或负数：

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

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