C / C++ 中快速向上取整整数除法

356

给定整数值 xy,C 和 C++ 都将商 q = x/y 返回为浮点等价物的 floor。我对一种返回 ceiling 的方法感兴趣。例如,ceil(10/5)=2ceil(11/5)=3

显然的方法涉及以下内容:

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

这需要额外的比较和乘法;而我看到的其他方法(实际使用过)涉及将其转换为floatdouble。是否有更直接的方法可以避免额外的乘法(或第二个除法)和分支,并且还可以避免将其转换为浮点数?


102
除法指令通常同时返回商和余数,因此无需进行乘法运算,只需使用 q = x/y + (x % y != 0); 即可。该语句已足够表达原意。 - phuclv
1
@LưuVĩnhPhúc,你真的需要把那个作为答案添加进去。我在Codility测试中使用了它作为我的答案。它非常有效,虽然我不确定答案中的模块部分是如何工作的,但它完成了任务。 - Zachary Kraus
3
@AndreasGrapentin,Miguel Figueiredo的下面的回答是在Lưu Vĩnh Phúc发表评论之前差不多一年前提交的。尽管我理解Miguel的解决方案非常吸引人和优雅,但我不倾向于在这么晚的时候更改已接受的答案。两种方法仍然可行。如果你对此有足够强烈的看法,我建议你通过给Miguel下面的答案点赞来表达支持。 - andand
2
奇怪的是,我没有看到任何合理的测量或分析提出的解决方案。你谈论了接近极限速度,但没有讨论架构、流水线、分支指令和时钟周期。 - Rado
1
参见:https://dev59.com/vrzpa4cB1Zd3GeqPRMKI - andand
显示剩余2条评论
11个回答

526

对于正数,当你想要找到x除以y的向上取整(q)时使用。

unsigned int x, y, q;

要对一个数字进行四舍五入并将其向上取整至最接近的指定数量的倍数,可以使用以下公式:

rounded_number = math.ceil(input_number / multiple) * multiple
q = (x + y - 1) / y;

或(避免 x+y 溢出)

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

9
对于负数,我认为C99规定了向零舍入,所以x/y是除法的上限。C90没有规定如何舍入,我不认为当前的C++标准有这个规定。 - David Thornley
6
请参考Eric Lippert的帖子:https://dev59.com/_nNA5IYBdhLWcg3wh-cC#926806 - Mashmagar
3
注意:这可能会溢出。但 ((long long)x + y - 1) / y 不会。虽然我的代码速度较慢,但如果您知道您的数字不会溢出,应该使用Sparky的版本。 - Jørgen Fogh
17
第二个有一个问题,当x等于0时。ceil(0/y) = 0,但它返回1。 - Omry Yadan
3
@OmryYadan这个表达式 x == 0 ? 0 : 1 + ((x - 1) / y) 能够安全且有效地解析吗? - jamesmstone
显示剩余4条评论

132

针对正数:

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

22
大多数常见架构的除法指令也会将余数包含在其结果中,因此这实际上只需要一次除法运算就能得到结果,并且速度非常快。 - phuclv
1
这是最优雅的解决方案。我已将其扩展到负数和向下/向上舍入 - Jan Schultke

66

Sparky的回答是解决这个问题的一种标准方法,但正如我在评论中所写的那样,你会面临溢出的风险。可以通过使用更宽的类型来解决这个问题,但如果你想除以long long怎么办?

Nathan Ernst提供了一种解决方案,但它涉及一个函数调用、一个变量声明和一个条件语句,这使得它不比OPs的代码更短,而且可能更慢,因为它更难优化。

我的解决方案是:

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

它会比OP的代码稍微快一点,因为处理器在执行取模和除法时使用相同的指令,编译器能够看到它们是等价的。至少gcc 4.4.1在x86上使用-O2标志时会执行此优化。

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

最后说明,除非你处于非常紧密的循环中且所有数据都在寄存器或L1缓存中,否则在现代计算机上这些内容都不重要。否则,所有这些解决方案速度都将相同,可能只有Nathan Ernst的解决方案会比较慢,如果需要从主存中获取函数时会明显变慢。


3
修复溢出的更简单方式是减少 y/y 的值:q = (x > 0)? 1 + (x - 1)/y: (x / y); - Ben Voigt
8
不,它不需要。正如我在答案中解释的那样,当你执行了除法运算后,使用百分号运算符是免费的。 - Jørgen Fogh
1
那么 q = x / y + (x % y > 0);? : 表达式更容易吗? - Han
1
这取决于你所说的“更容易”的含义。根据编译器的翻译方式,它可能会更快或更慢。我猜测会更慢,但我必须进行测量才能确定。 - Jørgen Fogh
1
我不认为添加分支指令会使其更快,实际上。 - einpoklum
显示剩余2条评论

26

你可以使用 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;
}

15
作为双重感叹号的一个有趣案例,你也可以使用 return res.quot + !!res.rem; :) 来表达。 - Sam Harwell
ldiv是否总是将参数提升为long long?这样做会有什么代价,向上转型或向下转型吗? - einpoklum
1
@einpoklum:std::div被重载为intlonglong longintmax_t(自C++11以来后两者);它是否在内部提升将是实现细节(我看不出为什么他们不会独立实现每个的强烈原因)。 ldiv会提升,但std::div不需要。 - ShadowRanger

15

对于正数和负数的 x 都有解,但仅对于正数的 y,且只需进行1次除法而无需分支:

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

请注意,如果x为正数,则除法朝向零,并且如果余数不为零,则应添加1。

如果x为负数,则除法朝向零,这就是我们所需要的,而且我们将不会添加任何东西,因为x%y不是正数。


有趣的是,由于y是常数的常见情况。 - Wolf
1
模运算需要除法,因此这里不仅仅是一次除法,但编译器可以将两个相似的除法优化为一个。 - M.kazem Akhgary
这条评论暗示现代架构可以使用一条指令进行除法和取模运算。当然,这仍然需要一个智能编译器。 - cubuspl42

12

这个怎么样?(需要y为非负数,所以在y没有非负性保证的罕见情况下不要使用它)

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

我将 y/y 简化为 1,消除了 x + y - 1 这个项以及出现溢出的任何可能性。

x 是无符号类型并且包含零时,我避免了 x - 1 的回绕。

对于有符号的 x,负数和零仍然合并成一个情况。

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


你的else语句总是返回0,不需要计算任何东西。 - Ruud Althuizen
2
@Ruud:不是这样的。考虑x=-45和y=4。 - Ben Voigt

9

我更愿意评论,但我的声望不够高。

据我所知,对于正参数和作为2的幂的除数,这是最快的方法(在CUDA中测试过):

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

对于一般的正参数,我通常这样处理:

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

看看在当代CUDA中,q = x/y + !!(x % y);q = x/y + (x % y == 0);以及q = (x + y - 1) / y;这些解决方案在性能上的表现如何,会很有趣。 - Greg Kramida
1
似乎 q = x/y + (x % y == 0); 应该改为 q = x/y + (x % y != 0); - Sean W

5

以下方法适用于正数或负数:

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

如果有余数,则检查xy是否同号,并相应地添加1


不适用于负x和正y。 - Alan Kałuża

4

用于有符号或无符号整数。

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);

零除数失败(与本地操作一样)。不会导致溢出。

相应的向下取整和模运算的constexpr实现可在此处找到,还提供了模板以选择必要的重载(作为完全优化和防止不匹配的符号比较警告):

https://github.com/libbitcoin/libbitcoin-system/wiki/Integer-Division-Unraveled


3

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接