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

新手上路,请多包涵

给定整数值 xy ,C 和 C++ 都返回商 q = x/y 浮点等效值的下限。我对一种返回天花板的方法感兴趣。例如, ceil(10/5)=2ceil(11/5)=3

显而易见的方法涉及以下内容:

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

这需要额外的比较和乘法;和我见过的其他方法(实际上使用)涉及强制转换为 floatdouble 。是否有更直接的方法可以避免额外的乘法(或二次除法)和分支,并且也避免转换为浮点数?

原文由 andand 发布,翻译遵循 CC BY-SA 4.0 许可协议

阅读 597
2 个回答

对于正数,您希望找到 x 除以 y 的上限 (q)。

 unsigned int x, y, q;

围观…

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

或(避免 x+y 中的溢出)

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

原文由 Sparky 发布,翻译遵循 CC BY-SA 4.0 许可协议

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

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

原文由 evoskuil 发布,翻译遵循 CC BY-SA 4.0 许可协议

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题