Keep Learning

伪程序员记录点滴

取整操作

问题

A,B都是整数并且 A>1, B>1,求 ┌ A/B ┐ 即 A/B 的上取整。

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

当不整除,返回值是 int(A/B) + 1

这个算法的一个应用:如果你有一个动态增长的缓冲区,增长的步长是 B,某一次缓冲区申请的大小是 A,这个时候,就可以用这个算法,计算出缓冲区的一个合适大小了,正好可以容纳A,并且不会过于得多,多余部分不会比B多。

方法

int( (A+B-1)/B )

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)