C/C++ 中整数除法的快速上限
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2745074/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fast ceiling of an integer division in C / C++
提问by andand
Given integer values xand y, C and C++ both return as the quotient q = x/ythe floor of the floating point equivalent. I'm interested in a method of returning the ceiling instead. For example, ceil(10/5)=2and ceil(11/5)=3.
给定整数值x和y，C 和 C++ 都返回q = x/y浮点等效值的商作为商。我对返回天花板的方法感兴趣。例如，ceil(10/5)=2和ceil(11/5)=3。
The obvious approach involves something like:
显而易见的方法包括：
q = x / y;
if (q * y < x) ++q;
This requires an extra comparison and multiplication; and other methods I've seen (used in fact) involve casting as a floator double. Is there a more direct method that avoids the additional multiplication (or a second division) and branch, and that also avoids casting as a floating point number?
这需要额外的比较和乘法；和我见过的其他方法（实际上使用过）涉及转换为 a floator double。是否有更直接的方法可以避免额外的乘法（或二次除法）和分支，并且也避免转换为浮点数？
回答by Sparky
For positive numbers
对于正数
unsigned int x, y, q;
To round up ...
为了圆...
q = (x + y - 1) / y;
or (avoiding overflow in x+y)
或（避免 x+y 溢出）
q = 1 + ((x - 1) / y); // if x != 0
回答by Miguel Figueiredo
For positive numbers:
对于正数：
q = x/y + (x % y != 0);
回答by J?rgen Fogh
Sparky's answer is one standard way to solve this problem, but as I also wrote in my comment, you run the risk of overflows. This can be solved by using a wider type, but what if you want to divide long longs?
Sparky 的答案是解决这个问题的一种标准方法，但正如我在评论中所写的那样，你冒着溢出的风险。这可以通过使用更宽的类型来解决，但是如果要除以long longs 呢？
Nathan Ernst's answer provides one solution, but it involves a function call, a variable declaration and a conditional, which makes it no shorter than the OPs code and probably even slower, because it is harder to optimize.
Nathan Ernst 的回答提供了一种解决方案，但它涉及一个函数调用、一个变量声明和一个条件，这使得它不比 OP 代码短，甚至可能更慢，因为它更难优化。
My solution is this:
我的解决方案是这样的：
q = (x % y) ? x / y + 1 : x / y;
It will be slightly faster than the OPs code, because the modulo and the division is performed using the same instruction on the processor, because the compiler can see that they are equivalent. At least gcc 4.4.1 performs this optimization with -O2 flag on x86.
它会比 OPs 代码稍微快一点，因为在处理器上使用相同的指令执行取模和除法，因为编译器可以看到它们是等效的。至少 gcc 4.4.1 在 x86 上使用 -O2 标志执行此优化。
In theory the compiler might inline the function call in Nathan Ernst's code and emit the same thing, but gcc didn't do that when I tested it. This might be because it would tie the compiled code to a single version of the standard library.
理论上，编译器可能会在 Nathan Ernst 的代码中内联函数调用并发出相同的内容，但是当我测试它时 gcc 没有这样做。这可能是因为它将编译后的代码绑定到标准库的单个版本。
As a final note, none of this matters on a modern machine, except if you are in an extremely tight loop and all your data is in registers or the L1-cache. Otherwise all of these solutions will be equally fast, except for possibly Nathan Ernst's, which might be significantly slower if the function has to be fetched from main memory.
最后要注意的是，这些在现代机器上都无关紧要，除非您处于非常紧密的循环中并且所有数据都在寄存器或 L1 缓存中。否则所有这些解决方案都将同样快，除了可能是 Nathan Ernst 的，如果必须从主内存中获取函数，它可能会明显变慢。
回答by Nathan Ernst
You could use the divfunction in cstdlib to get the quotient & remainder in a single call and then handle the ceiling separately, like in the below
您可以使用divcstdlib 中的函数在一次调用中获取商和余数，然后分别处理天花板，如下所示
#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;
}
回答by Ben Voigt
How about this? (requires y non-negative, so don't use this in the rare case where y is a variable with no non-negativity guarantee)
这个怎么样？（需要 y 非负，所以不要在 y 是一个没有非负保证的变量的极少数情况下使用它）
q = (x > 0)? 1 + (x - 1)/y: (x / y);
I reduced y/yto one, eliminating the term x + y - 1and with it any chance of overflow.
我减少y/y到一个，消除了这个词，x + y - 1并且有任何溢出的机会。
I avoid x - 1wrapping around when xis an unsigned type and contains zero.
我避免x - 1环绕 whenx是无符号类型并且包含零。
For signed x, negative and zero still combine into a single case.
对于 signed x，负数和零仍然合并为一个案例。
Probably not a huge benefit on a modern general-purpose CPU, but this would be far faster in an embedded system than any of the other correct answers.
在现代通用 CPU 上可能不是一个巨大的好处，但这在嵌入式系统中会比任何其他正确答案快得多。
回答by RiaD
There's a solution for both positive and negative xbut only for positive ywith just 1 division and without branches:
有正负两种解决方案，x但仅适用y于只有 1 个部门且没有分支的正解决方案：
int ceil(int x, int y) {
return x / y + (x % y > 0);
}
Note, if xis positive then division is towards zero, and we should add 1 if reminder is not zero.
注意，如果x为正则除法趋于零，如果提醒不为零，我们应该加1。
If xis negative then division is towards zero, that's what we need, and we will not add anything because x % yis not positive
如果x为负，则除法趋于零，这就是我们需要的，我们不会添加任何内容，因为x % y不是正数
回答by Mark Conway
This works for positive or negative numbers:
这适用于正数或负数：
q = x / y + ((x % y != 0) ? !((x > 0) ^ (y > 0)) : 0);
If there is a remainder, checks to see if xand yare of the same sign and adds 1accordingly.
如果有余数，则检查x和y是否具有相同的符号并相应地添加1。
回答by Atif Hussain
simplified generic form,
简化的通用形式，
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)
For a more generic answer, C++ functions for integer division with well defined rounding strategy
对于更通用的答案，用于整数除法的 C++ 函数具有明确定义的舍入策略
回答by Anroca
I would have rather commented but I don't have a high enough rep.
我宁愿发表评论，但我没有足够高的代表。
As far as I am aware, for +ve & pow of 2 this is the fastest way (tested in CUDA)
据我所知，对于 2 的 +ve & pow 这是最快的方法（在 CUDA 中测试）
//example y=8
q = (x >> 3) + !!(x & 7);
otherwise (also +ve only) I'd tend to do it like so:
否则（也只有 +ve）我倾向于这样做：
q = x/y + !!(x % y);
回答by dhb
Compile with O3, The compiler performs optimization well.
用O3编译，编译器优化的很好。
q = x / y;
if (x % y) ++q;
