给定整数值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类型的类型转换。有没有一种更直接的方法可以避免额外的乘法(或二次除法)和分支,同时也避免将类型转换为浮点数?
给定整数值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类型的类型转换。有没有一种更直接的方法可以避免额外的乘法(或二次除法)和分支,同时也避免将类型转换为浮点数?
当前回答
对于正数:
q = x/y + (x % y != 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);
零除数失败(与本机操作一样)。不能导致溢出。
对应的floor和modulo constexpr实现在这里,以及模板选择必要的重载(作为完全优化和防止不匹配的符号比较警告):
https://github.com/libbitcoin/libbitcoin-system/wiki/Integer-Division-Unraveled
对于正数:
q = x/y + (x % y != 0);
对于正x和负x都有一个解,但只对正y有一个除法,没有分支:
int div_ceil(int x, int y) {
return x / y + (x % y > 0);
}
注意,如果x是正的,那么除法趋向于零,如果提醒符不为零,我们应该加1。
如果x为负,除法趋向于0,这就是我们需要的,我们不加任何东西,因为x % y不为正
这个怎么样?(要求y是非负的,所以在y是一个没有非负保证的变量的罕见情况下不要使用这个)
q = (x > 0)? 1 + (x - 1)/y: (x / y);
我将y/y化简为1,消除了x + y - 1项,并消除了溢出的可能性。
当x是无符号类型且包含0时,我避免x - 1自动换行。
对于有符号的x,负和零仍然合并为一种情况。
在现代通用CPU上可能没有太大的好处,但在嵌入式系统中,这比其他任何正确答案都要快得多。
我本想发表评论,但我的知名度不够高。
据我所知,对于正参数和2的幂的除数,这是最快的方法(在CUDA中测试过):
//example y=8
q = (x >> 3) + !!(x & 7);
对于一般的正面论证,我倾向于这样做:
q = x/y + !!(x % y);