向上取整的高效实现

在编程中，我们经常需要对除法结果进行向上取整。虽然可以使用 ceil() 函数，但在处理整数时，直接使用整数运算不仅效率更高，还能避免浮点数带来的精度问题。

向上取整公式

对于两个正整数 a 和 b，向上取整 ceil(a/b) 可以用以下整数运算实现：

原理详解

这个公式巧妙地利用了整数除法向下取整的特性。核心思想是：先给被除数 a 增加一个“偏移量”，使得在有余数时，商能够增加1。

1. 直观理解

• 当 a 能被 b 整除时 (如 a=10, b=5)

  • a / b 的结果为 2。
  • 公式计算：(10 + 5 - 1) / 5 = 14 / 5 = 2。结果正确。
  • + (b-1) 这个操作不足以让商增加1。

• 当 a 不能被 b 整除时 (如 a=11, b=5)

  • 11 / 5 向上取整应为 3。
  • 公式计算：(11 + 5 - 1) / 5 = 15 / 5 = 3。结果正确。
  • + (b-1) 恰好将 a “凑”到了下一个 b 的倍数，从而使商增加了1。

2. 数学证明

设 $a = qb + r$，其中 $q = \lfloor \frac{a}{b} \rfloor$ 且 $0 \le r < b$。

我们将 $a$ 代入公式，并对整数除法结果（即向下取整 $\lfloor \cdot \rfloor$）进行分析：

我们根据余数 $r$ 的值进行讨论：

• 情况一：$r = 0$ (a 能被 b 整除)

  • 此时向上取整结果应为 $q$。
  • 代入上式：$q + 1 + \lfloor \frac{0-1}{b} \rfloor = q + 1 + \lfloor \frac{-1}{b} \rfloor$。
  • 因为 $b$ 是正整数 ($b \ge 1$)，所以 $\lfloor \frac{-1}{b} \rfloor = -1$。
  • 最终结果为 $q + 1 + (-1) = q$。证明成立。

• 情况二：$r > 0$ (a 不能被 b 整除)

  • 此时向上取整结果应为 $q+1$。
  • 因为 $1 \le r < b$，所以 $0 \le r-1 < b-1$。
  • 因此，$0 \le \frac{r-1}{b} < 1$。
  • 所以 $\lfloor \frac{r-1}{b} \rfloor = 0$。
  • 最终结果为 $q + 1 + 0 = q+1$。证明成立。

综上所述，该公式对于所有正整数 a 和 b 都能正确计算向上取整。

C++ 代码示例

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14

        #include <iostream>

void print_ceil_division(int a, int b) {
    // 使用高效的整除方法实现向上取整
    int result = (a + b - 1) / b;
    std::cout << "ceil(" << a << " / " << b << ") = " << result << std::endl;
}

int main() {
    print_ceil_division(11, 5); // 不能整除的例子
    print_ceil_division(10, 5); // 能整除的例子
    return 0;
}

    

输出结果：

ceil(11 / 5) = 3
ceil(10 / 5) = 2

注意事项

1. 适用范围：此方法仅适用于正整数。如果 a 或 b 可能为负数，需要根据具体场景的取整定义进行调整。
2. 溢出风险：当 a 和 b 的值很大时，a + b - 1 有可能导致整数溢出。在这种情况下，应使用范围更大的数据类型，如 long long。

模板的代码

        
1
2
3
4
5
6

        // 向上取整

unsigned long long  myceil(unsigned long long  a ,unsigned long long b) {
    return (a+b-1)/b;
}