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

当前回答

这适用于正数或负数:

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

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

其他回答

对于正数:

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

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

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

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

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

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

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

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

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

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

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

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

这适用于正数或负数:

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

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

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

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

推荐文章