首页 / 软件开发 / 数据结构与算法 / A/B向上取整的方法

A/B向上取整的方法2010-06-09孙雪青1.问题

A,B都是整数并且 A>1, B>1

求 ┌ A/B ┐ 即 A/B 的上取整。

当 A/B 整除，往上取整返回值 为 A/B。

当 不整除，返回值是 int（A/B） + 1

这个算法的一个应用：如果你有一个动态增长的缓冲区，增长的步长是 B,

某一次缓冲区申请的大小是 A，这个时候，就可以用这个算法，计算出缓冲区的一个合

适大小了，正好可以容纳A，并且不会过于得多，多余部分不会比B多。

2.方法

int（ （A+B-1）/B ）

3.HUNTON 的证明

上取整用UP表示

由于A>1、B>1，且A、B都是整数，所以可以设A=NB+M

其中N为非负整数，M为0到B-1的数，则

A/B = N + M/B

（A+B-1）/B = N + 1 + （M - 1）/B;

当M为0时，

UP（A/B） = N，

int（（A+B-1）/B） = N + int（1 - 1/B） = N

当M为1到B-1的数时，0 <= M-1 <= B-2

UP（A/B） = N + 1，

int（（A+B-1）/B） = N + 1 + int（（M-1）/B） = N + 1

所以对A>1、B>1的整数A、B都有：

UP（A/B） = int（（A+B-1）/B）