Lcc内存对齐代码

今天看lcc源码内存对齐时看到一个roundup(x,n)宏

#define roundup(x,n) (((x)+((n)-1))&(~((n)-1)))

从字面意思看这个宏应该是用来向上取整的。但是(x+n-1)&(~(n-1))的确让人一时傻眼了。

这里要从头说起，首先roundup(x,n)的作用就是向上取整，即求出最小的a * n，使得a*n >= x，即

x = a * n - b (0 <= b < n)

这里就要引入小学时的余数概念了：

除数 × 商 = 被除数 - 余数

即对于任意两个正整数x和n，总存在整数a和b，使得:

x = a * n + b (0 <= b < n)

在C语言中求a和b非常简单：

a = x / n;
b = x % n;

所以，如果把roundup(x,n)转换，就可以求a*n了：

x = a * n - b (0 <= b < n)
x+n = a * n - b + n
x+n = a*n + (n-b) (0 < (n-b) <= n)
x+n-1 = a*n + (n-b-1) (0 <= (n-b-1) < n)

于是：

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

到这里就可以算出a*n了，但是很明显roundup(x,n)在这里继续对公式进行优化。

因为n是内存块的单位，一定是2的幂，于是有如下的特性：

• 设n = 2^m，则m = n - 1
• n的二进制必然是100...的形态，其中有m个0
• 对于n的乘除操作，可以用左移右移完成

所以看回算式

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

可以看作是(x+n-1)右移m个位，在左移m个位，也就是把最低的m个位清零就可以了。

而从上面的属性可以知道，n-1的二进制必然是111...的形态，其中有m个1，所以清零只要对m的反码进行与操作就可以了。

于是

a*n = (x+n-1)&(~(n-1))

多么优美的一行代码，虽然可读性不高，但是理解了之后心中还是会产生无比的敬仰，这就是编程的魔力啊，作者就像在尽情的揉捏语言，这感觉一定很棒吧！