利用ROUNDUP函数进行内存对齐

内存对齐：

比如一个内存单元的长度为2，为了存取方便我们应该尽量把数据放在2的倍数的位置上（如位置0，2，4，6等），此时称该数据的位置是与某个值（2）对齐的。如果放在了没对齐的地方（比如位置3）上，该数据可能跨过了一次能读取的跨度，就必须读两次才行。

为了杜绝这种低效行为，我们使用一个函数ROUNDUP(n, size)来对原地址n进行修改，从而实现内存对齐。

举个例子，ROUNDUP(9，2)=10，也就是把本来的位置9改成对齐到位置10。

 

其算法通常是这样的： #define ROUNDUP(x,n) ((x+(n-1))&(~(n-1)))，n为对齐的大小

 

下面对该算法进行一下解释：

我们知道，对于两个正整数 x, n 总存在整数 q, r 使得

x = nq + r, 其中  0<= r <n                  //最小非负剩余表示法

q, r 是唯一确定的。q = [x/n], r = x - n[x/n]. 这个是我们所熟悉的带余除法的一个简单形式。在 c 语言中， q, r 容易计算出来： q = x/n, r = x % n.

所谓把 x 按 n 对齐指的是：若 r=0, 取返回值为qn, 若 r>0, 取 (q+1)n.

这也相当于把 x 表示为：

x = nq + r', 其中 -n < r' <=0                //最大非正剩余表示法   

nq 是我们所求。关键是如何用 c 语言计算它。由于我们能处理标准的带余除法，所以可以把这个式子转换成一个标准的带余除法，然后加以处理：

x+n = qn + (n+r')，其中 0<n+r'<=n            //最大非正剩余

x+n-1 = qn + (n+r'-1), 其中 0<= n+r'-1 <n    //最小非负剩余

所以 qn = [(x+n-1)/n]n.（当然也可表为x+n-1-(n+r'-1)） 用 c 语言计算就是：

((x+n-1)/n)*n

若 n 是 2 的方幂, 比如 2^m，则除为右移 m 位，乘为左移 m 位。所以把 x+n-1 的最低 m 个二进制位清 0就可以了。得到：

(x+n-1) & (~(n-1))

注意上面这个式子中对n-1操作时是对表示为二进制形式的n-1进行处理。

比如n=8，那么x+n-1整处8后再乘以8（相当于把余数抹掉）的操作就是先由8==1000(二进制)得到n-1==0111，然后取反为11111111 11111111 11111111 11111000，将x+n-1与之求位的与运算即可（即把x+n-1的二进制表示数的最后三位抹成零）。

如果n不是2的幂，则不能采用位运算的方法，可以采用普通的十进制方法。

size_t round_low(size_t x, size_t n) {
    return x - (x% n);
}
size_t round_up(size_t x,size_t n) {
    return (x + n - 1) - ((x + n - 1) % N);
}