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

围捕…

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

或(避免X+Y溢出)

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

对于正数:

    q = x/y + (x % y != 0);

Sparky的答案是解决这个问题的一种标准方法,但是正如我在我的评论中所写的,你会冒溢出的风险。这可以通过使用更宽的类型来解决,但是如果你想划分 long long S?

NathanErnst的答案提供了一个解决方案,但它涉及函数调用、变量声明和条件,这使得它不短于ops代码,甚至可能更慢,因为它更难优化。

我的解决方案是:

q = (x % y) ? x / y + 1 : x / y;

它将比ops代码快一点,因为模块和除法是使用处理器上的相同指令执行的,因为编译器可以看到它们是等效的。至少GCC4.4.1在x86上使用-o2标志执行此优化。

理论上,编译器可能会在NathanErnst的代码中内联函数调用并发出相同的东西,但当我测试它时,gcc没有这样做。这可能是因为它将编译后的代码绑定到标准库的单个版本。

最后一点要注意的是,在现代机器上,这些都不重要,除非您处于一个非常紧密的循环中,并且所有数据都在寄存器或一级缓存中。否则,所有这些解决方案都将同样快速,除了可能是Nathan Ernst的解决方案,如果必须从主内存中提取函数,那么这个解决方案可能会慢得多。

你可以使用 div cstdlib中的函数在单个调用中获取商余数,然后分别处理上限,如下所示

#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;
}

这个怎么样?(要求Y非负,因此在Y为无非负性保证的变量的情况下,不要使用此选项)

q = (x > 0)? 1 + (x - 1)/y: (x / y);

我减少了 y/y 第一,取消术语 x + y - 1 有了它,任何溢出的机会。

我避免 x - 1 什么时候包装 x 是无符号类型,包含零。

签字 X ,负和零仍然合并为一个案例。

在现代通用CPU上,这可能不是一个巨大的好处,但在嵌入式系统中,这比任何其他正确答案都要快得多。

有正负两种解决方案 x 但只是为了积极 y 只有一个部门,没有分支机构:

int ceil(int x, int y) {
    return x / y + (x % y > 0);
}

注意,如果 X 是正的,那么除法是朝零的,如果提醒不是零,我们应该加1。

如果 X 是负的,那么除法是朝零的,这就是我们需要的,我们不会加任何东西,因为 x % y 不是正面的

这适用于正数或负数。

q = x/y+((x%y!=0)?!((x>0)^(y>0)):0);

如果有余数,检查x和y是否相同,并相应地加1。

简化的通用形式,

int div_up(int n, int d) {
    return n / d + (((n < 0) ^ (d > 0)) && (n % d));
} //i.e. +1 iff (not exact int && positive result)

对于更一般的答案, C++ functions for integer division with well defined rounding strategy

我宁愿发表评论,但我没有足够高的代表。

据我所知,对于+ve&pow的2,这是最快的方法(在CUDA中测试)

//example y=8
q = x >> 3 + !!(x & 7);

否则(也只是+ve),我倾向于这样做:

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