一尘不染

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

algorithm

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

显而易见的方法包括:

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

这需要额外的比较和乘法。我见过的(实际上使用过的)其他方法都涉及将其转换为a
floatdouble。有没有更直接的方法来避免额外的乘法(或第二除法)和分支,并且还避免将其转换为浮点数?


阅读 359

收藏
2020-07-28

共1个答案

一尘不染

对于正数

unsigned int x, y, q;

舍入…

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

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

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