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

Question

给定整数值 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 。是否有更直接的方法可以避免额外的乘法（或二次除法）和分支，并且也避免转换为浮点数？

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

Answer 1

对于正数，您希望找到 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 许可协议

Answer 2

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

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 许可协议