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

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

显而易见的方法包括:

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

这需要额外的比较和乘法; 和我见过的其他方法(事实上使用)涉及到作为一个floatdouble铸造。 有没有一个更直接的方法,避免额外的乘法(或第二个分裂)和分支,这也避免铸造为浮点数?

总结…

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

或者(避免x + y溢出)

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

Sparky的答案是解决这个问题的一个标准方法,但正如我在我的评论中写道的那样,你冒着溢出的风险。 这可以通过使用更广泛的types来解决,但是如果要分割long long的types呢?

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

我的解决办法是:

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

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

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

最后要说的是,除非您处于一个非常紧密的循环中,并且所有的数据都在寄存器或L1caching中,否则在现代机器上这些都不重要。 否则,所有这些解决scheme将同样快速,除了可能Nathan Ernst的,如果function必须从主存储器取得,这可能会明显较慢。

对于正数:

  q = x/y + (x % y != 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; } 

这个怎么样? (要求y是非负数,所以不要在极less数情况下使用y,这里y是一个没有非负性保证的variables)

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

我把y/y减less到1,消除了x + y - 1这个词,并且有任何溢出的机会。

x是一个无符号types并且包含零时,我避免x - 1环绕。

对于有符号的x ,负数和零仍然合并成一个个案。

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

有一个正面和负面的x解决scheme,但只有正面的y只有1个分裂,没有分支:

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

注意,如果x是正的,那么除法是趋向零,如果提醒不是零,我们应该加1。

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

这适用于正数或负数。

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

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

简化的通用forms,

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

对于更通用的答案, C ++函数用于整数除法,具有明确的舍入策略