C / C中整数除法的快速上限-Java 学习之路

213

给定整数值 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 . 是否有更直接的方法可以避免额外的乘法（或第二个除法）和分支，并且还可以避免作为浮点数进行转换？

9 回答

2
围捕......
```
q = (x + y - 1) / y;
```
或（避免x y溢出）
```
q = 1 + ((x - 1) / y); // if x != 0
```
回复于 2024-04-29T15:20:19+08:00
12
对于正数：
```
q = x/y + (x % y != 0);
```
回复于 2024-04-29T15:20:19+08:00
331
Sparky的答案是解决这个问题的一种标准方法，但正如我在评论中写的那样，你冒着溢出的风险 . 这可以通过使用更宽的类型来解决，但是如果你想要划分 long long s呢？

Nathan Ernst的答案提供了一个解决方案，但它涉及函数调用，变量声明和条件，这使得它不比OP代码短，甚至可能更慢，因为它更难以优化 .

我的解决方案是：
```
q = (x % y) ? x / y + 1 : x / y;
```
它会比OPs代码略快，因为模数和除法是在处理器上使用相同的指令执行的，因为编译器可以看到它们是等价的 . 至少gcc 4.4.1在x86上使用-O2标志执行此优化 .

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

最后要注意的是，在现代机器上，这一切都不重要，除非您处于非常紧凑的循环中并且所有数据都在寄存器或L1缓存中 . 否则所有这些解决方案都会同样快，除了可能是Nathan Ernst之外，如果必须从主存储器获取该函数，这可能会明显变慢 .
回复于 2024-04-29T15:20:19+08:00

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

回复于 2024-04-29T15:20:19+08:00

56
这个怎么样？（要求y为非负数，所以在极少数情况下不要使用它，其中y是一个没有非负性保证的变量）
```
q = (x > 0)? 1 + (x - 1)/y: (x / y);
```
我将 y/y 减少为1，消除了术语 x + y - 1 ，并且有任何溢出的可能性 .

当 x 是无符号类型且包含零时，我避免 x - 1 回绕 .

对于签名 x ，负数和零仍然合并为一个案例 .

对于现代通用CPU来说可能不是一个巨大的好处，但在嵌入式系统中，这比任何其他正确的答案要快得多 .
回复于 2024-04-29T15:20:19+08:00
16
有一个正面和负面的解决方案 x 但只有正 y 只有1个分区且没有分支：
```
int ceil(int x, int y) {
    return x / y + (x % y > 0);
}
```
注意，如果 x 为正，那么除法为零，如果提醒不为零，我们应该加1 .

如果 x 为负，则除法为零，这就是我们需要的，我们不会添加任何东西，因为 x % y 不是正数
回复于 2024-04-29T15:20:19+08:00
3

这适用于正数或负数 .

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

如果有余数，则检查x和y是否具有相同的符号并相应地加1 .

回复于 2024-04-29T15:20:19+08:00
0
简化的通用形式，
```
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
回复于 2024-04-29T15:20:19+08:00
5
我宁可评论，但我没有足够高的代表 .

据我所知，对于ve＆pow of 2，这是最快的方式（在CUDA中测试）
```
//example y=8
q = x >> 3 + !!(x & 7);
```
否则（也是唯一的）我倾向于这样做：
```
q = x/y + !!(x % y);
```
回复于 2024-04-29T15:20:19+08:00

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

9 回答

相关问题