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

2021-12-06 00:00:00 algorithm math c c++

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

Given integer values x and y, C and C++ both return as the quotient q = x/y the floor of the floating point equivalent. I'm interested in a method of returning the ceiling instead. For example, ceil(10/5)=2 and ceil(11/5)=3.

显而易见的方法包括:

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

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

This requires an extra comparison and multiplication; and other methods I've seen (used in fact) involve casting as a float or double. Is there a more direct method that avoids the additional multiplication (or a second division) and branch, and that also avoids casting as a floating point number?

推荐答案

对于正数

unsigned int x, y, q;

四舍五入...

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

或(避免 x+y 溢出)

or (avoiding overflow in x+y)

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

相关文章