C++---向上取整

1. 什么是向上取整（Ceiling）

向上取整（Ceiling）是数学中的一个基本概念，表示取大于或等于某个数的最小整数。
数学符号是：⌈x⌉\lceil x \rceil⌈x⌉

例子：

• ⌈2.3⌉=3\lceil 2.3 \rceil = 3⌈2.3⌉=3
• ⌈2.0⌉=2\lceil 2.0 \rceil = 2⌈2.0⌉=2
• ⌈−2.3⌉=−2\lceil -2.3 \rceil = -2⌈−2.3⌉=−2 （注意不是 -3，因为 -2 比 -2.3 大）
• ⌈−2.0⌉=−2\lceil -2.0 \rceil = -2⌈−2.0⌉=−2

对比：向下取整（floor）：取小于或等于 x 的最大整数四舍五入（round）：根据小数部分决定向上或向下取整

2. C++ 中的除法默认是“向零截断”

在 C++ 中，两个整数相除 / 会执行向零截断（truncate towards zero）：

• 正数：等价于向下取整
• 负数：等价于向上取整

cout <<7/3<< endl;// 2（7/3=2.333，向零截断） cout <<-7/3<< endl;// -2（不是 -3）

这意味着：

• 直接用 / 不能直接得到数学上的向上取整结果
• 需要额外处理才能实现真正的向上取整

3. 实现向上取整的三种主流方法

3.1 使用 <cmath> 中的 std::ceil

C++ 标准库提供了 ceil 函数，定义在 <cmath> 中：

#include<iostream>#include<cmath>usingnamespace std;intmain(){double x =7.0/3.0; cout <<ceil(x)<< endl;// 3double y =-7.0/3.0; cout <<ceil(y)<< endl;// -2}

特点：

• 支持浮点数，能正确处理负数
• 缺点：需要先转换成浮点类型，否则整数除法已经截断
• 有精度误差风险：ceil(8.999999999) 可能得到 8 而不是 9

3.2 整数公式法（适用于正数）

公式：⌈ab⌉=a+b−1b(a,b>0)\lceil \frac{a}{b} \rceil = \frac{a + b - 1}{b} \quad (a, b > 0)⌈ba​⌉=ba+b−1​(a,b>0)

原理：

• 如果 a 能被 b 整除，那么 a + b - 1 除以 b 仍是 a / b
• 如果不能整除，a + b - 1 会把分子推到下一个能整除的区间

例子：

int a =7, b =3; cout <<(a + b -1)/ b << endl;// (7+3-1)/3 = 9/3 = 3 ✅int a2 =6, b2 =3; cout <<(a2 + b2 -1)/ b2 << endl;// (6+3-1)/3 = 8/3 = 2 ✅

适用范围：

• a、b 均为正数
• 对于负数，需要额外调整

3.3 位运算优化法（b 是 2 的幂）

如果 b 是 2 的幂，可以用位运算代替除法，效率更高：
⌈a2k⌉=(a+(1<<k)−1)>>k\lceil \frac{a}{2^k} \rceil = (a + (1 << k) - 1) >> k⌈2ka​⌉=(a+(1<<k)−1)>>k

例子：

int a =17, k =3;// b = 8int ceil_div =(a +(1<< k)-1)>> k;// (17 + 8 - 1) >> 3 = 24 >> 3 = 3 ✅

原理：

• (1 << k) - 1 生成 k 个 1 的掩码
• 加法后右移 k 位相当于整除 2^k

4. 边界情况处理

4.1 a 或 b 为 0

• 如果 b = 0：无意义（除零错误）
• 如果 a = 0：向上取整结果为 0

4.2 负数处理

通用安全公式（支持负数）：

intceil_div(int a,int b){if(b ==0)throwruntime_error("Division by zero");if((a >0&& b >0)||(a <0&& b <0)){// 同号：用 (a + b - 1) / breturn(a + b -1)/ b;}else{// 异号：直接除（向零截断等价于向上取整）return a / b;}}

5. 性能对比

6. 实战应用场景

6.1 分页计算

int total_items =100;int page_size =10;int pages =(total_items + page_size -1)/ page_size;// 10 页

6.2 数组分块

int n =17;int block_size =5;int blocks =(n + block_size -1)/ block_size;// 4 块

6.3 二分查找中的边界计算

LeetCode 2300：

longlong t =(success + i -1)/ i -1;

这里 (success + i - 1) / i 就是对 success / i 向上取整。

7. 完整代码示例

#include<iostream>#include<cmath>#include<stdexcept>usingnamespace std;// 通用向上取整函数（支持负数）intceil_div(int a,int b){if(b ==0)throwruntime_error("Division by zero");if((a >0&& b >0)||(a <0&& b <0)){return(a + b -1)/ b;}else{return a / b;}}// 位运算优化版（b 是 2 的幂）intceil_pow2(int a,int k){return(a +(1<< k)-1)>> k;}intmain(){// 测试正数 cout <<ceil_div(7,3)<< endl;// 3 cout <<ceil_div(6,3)<< endl;// 2// 测试负数 cout <<ceil_div(-7,3)<< endl;// -2 cout <<ceil_div(7,-3)<< endl;// -2 cout <<ceil_div(-7,-3)<< endl;// 3// 测试位运算版本 cout <<ceil_pow2(17,3)<< endl;// 3 (17/8=2.125)// 测试标准库函数 cout <<ceil(7.0/3.0)<< endl;// 3 cout <<ceil(-7.0/3.0)<< endl;// -2return0;}

8. 总结与建议

1. 正数场景：
   • 用 (a + b - 1) / b 最安全高效
   • 如果 b 是 2 的幂，用位运算 (a + (1 << k) - 1) >> k 更快
2. 负数场景：
   • 用通用公式 ceil_div(a, b)
   • 或直接用 std::ceil((double)a / b)
3. 性能敏感场景：
   • 优先考虑位运算（如果适用）
   • 否则用整数公式法
4. 精度敏感场景：
   • 避免直接用浮点数计算，优先整数公式

生活本来就很精彩。只不过有人没发现自己是作者，没发现他们可以按自己的想法创作。 —约翰·史特列奇