给定整数值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类型的类型转换。有没有一种更直接的方法可以避免额外的乘法(或二次除法)和分支,同时也避免将类型转换为浮点数?
当前回答
使用O3编译,编译器优化性能良好。
q = x / y;
if (x % y) ++q;
其他回答
对于正数,求x除以y的上限q。
unsigned int x, y, q;
把…
q = (x + y - 1) / y;
或(避免x+y溢出)
q = 1 + ((x - 1) / y); // if x != 0
您可以使用cstdlib中的div函数在一次调用中获得商和余数,然后分别处理天花板,如下所示
#include <cstdlib>
#include <iostream>
int div_ceil(int numerator, int denominator)
{
std::div_t res = std::div(numerator, denominator);
return res.rem ? (res.quot + 1) : res.quot;
}
int main(int, const char**)
{
std::cout << "10 / 5 = " << div_ceil(10, 5) << std::endl;
std::cout << "11 / 5 = " << div_ceil(11, 5) << std::endl;
return 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 > 0) ^ (y > 0)) : 0);
如果有余数,则检查x和y是否具有相同的符号,并相应地加1。
使用O3编译,编译器优化性能良好。
q = x / y;
if (x % y) ++q;