C / C++ 中快速向上取整整数除法

Question

C / C++ 中快速向上取整整数除法

356

给定整数值 x 和 y，C 和 C++ 都将商 q = x/y 返回为浮点等价物的 floor。我对一种返回 ceiling 的方法感兴趣。例如，ceil(10/5)=2 和 ceil(11/5)=3。

显然的方法涉及以下内容：

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

这需要额外的比较和乘法；而我看到的其他方法（实际使用过）涉及将其转换为float或double。是否有更直接的方法可以避免额外的乘法（或第二个除法）和分支，并且还可以避免将其转换为浮点数？

- andand

102

除法指令通常同时返回商和余数，因此无需进行乘法运算，只需使用 q = x/y + (x % y != 0); 即可。该语句已足够表达原意。 - phuclv

1

@LưuVĩnhPhúc，你真的需要把那个作为答案添加进去。我在Codility测试中使用了它作为我的答案。它非常有效，虽然我不确定答案中的模块部分是如何工作的，但它完成了任务。 - Zachary Kraus

3

@AndreasGrapentin，Miguel Figueiredo的下面的回答是在Lưu Vĩnh Phúc发表评论之前差不多一年前提交的。尽管我理解Miguel的解决方案非常吸引人和优雅，但我不倾向于在这么晚的时候更改已接受的答案。两种方法仍然可行。如果你对此有足够强烈的看法，我建议你通过给Miguel下面的答案点赞来表达支持。 - andand

2

奇怪的是，我没有看到任何合理的测量或分析提出的解决方案。你谈论了接近极限速度，但没有讨论架构、流水线、分支指令和时钟周期。 - Rado

1

参见：https://dev59.com/vrzpa4cB1Zd3GeqPRMKI - andand

显示剩余2条评论

11个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dhb · Answer 1

使用O3编译，编译器优化能力强。

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