1.

在c语言中，我们经常会看到一个关于内存对齐的宏：

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

或者类似

#define ALIGN(x) = (((x)+3)&~3

第一个宏就是所谓的把 x 按 n 对齐，第二个宏只不过是把n带入具体的数字，我们可以说是把x 按 4 对齐。

宏计算的结果为，把 x 按 n 对齐时，所需要的内存大小

举例：

如果把3 按 4 对齐，那么所需内存的大小为 4，填充为1

如果把5 按 4 对齐，那么所需内存的大小为 8，填充为3

2.

要理解这个宏的具体计算原理，首先我们要知道对任意整数都有如下公式：

b = ac + r; 0<= r < a;

其中所有值都为整数。

随便带入几个数方便有一个直观的认识：若b = 8，c = 2，则 a = 3，r = 2，即 8=3 * 2 + 2；

其中的r，就是我们通常概念中的余数，同时我们可以把它叫做 最小非负剩余。仔细理解这个概念，有助于接下来的推理。

用c 语言或者其他类似语言进行计算时，我们可以得到：

a = b/c; r= b - b/a;

注意：我们讨论的所有的数字都是整数，编程语言通常在计算整数除法时，都遵守一个原则，那就是小数部分全部舍弃，

即8/3  2.67，编程语言中8/3=2，这里不会四舍五入。

由最小非负剩余我们可以来试着写出最大非正剩余，即

x = qn + m; -n< m <=0;

其中r叫做最大非正剩余。

同样，随便带入几个数方便有一个直观的认识：若x = 5，n = 8，则 q = 1，m = -3，即 5=1 * 8 - 3；

推导到这里，我们发现，所谓的最大非正剩余，就是我们要讨论的核心，即把x 按 n 对齐，m 的绝对值就是我们把x 按 n 对齐时，要填充的大小，同时我们的宏要求得的既是qn。

现在我们要将最大非正剩余转换成最小非负剩余，这样方便我们求qn

为了达成这个目的，我们做如下推导：

x = qn + m; -n< m <=0;

x + n = qn + m + n; 0 < m <=n;

x + n - 1 = qn + ( m + n - 1); 0=< m <n;

同时观察最大非正剩余公式：

b = ac + r; 0<= r < a;

即:

ac = qn；

b = x + n - 1;

同时在最小非负剩余的讨论中，我们还知道 a = b/c 

可得 qn = ac = b/c*c = (x + n - 1)/n*n;

3.

接下来简单介绍一些推导过程涉及到的位运算，以帮助我们把最后的推导完成。

左移：<<

作用：相当于位运算中的乘法，x 左移 n位，即 x * 2的n次幂

举例：

0011 左移 两位 为1100，即

3 << 2 = 1100 = 3 * 2的2次幂 = 3 * 4 = 12

右移：>>

作用：相当于位运算中的除法，x 右移 n位，即 x / 2的n次幂

举例：

1111 右移 两位 为0011，即

15 >> 2 = 0011 = 15 / 2的2次幂 = 15 / 4 = 3

注意，这里是我们之前讨论的整数除法，并且不会四舍五入

左移右移这两个操作有一个值得注意的地方是，移位后空位补零，也就是说1111（十进制15），右移后再左移，不会变回15，因为右移时被移除的末两位在左移后会被步零

1111 >> 2 = 0011

0011 << 2 = 1100

所以连续的右移再左移，相当于是清理了这个数字的末尾两位。

再看我们求得的公式：qn =  (x + n - 1)/n*n;

内存对齐时，通常对齐数都是2 的某次幂，也就是说我们通常都会按照4 对齐或者8对齐，在这个前提下

我们可以限定n 的范围，即 n 为 2 的某次幂

由此我们又可以得到一个结论，qn =  (x + n - 1)/n*n 相当于将 (x + n - 1) 右移 了几位后，再左移，也就是说将(x + n - 1)末尾几位清零后，得到的结果便是qn

那么是末尾几位呢？答案很明显，是以2为底，n 的对数。

举例来说就是，按 4 对齐时，要将 (x + n - 1) 的末尾 2位清零；按 8 对齐时，要将 (x + n - 1) 的末尾 3位清零。

可以带入具体数字计算一下，比如，把3 按 4 对齐，带入公式得 3 + 4 - 1 = 6，6 得二进制数据为 0110，n = 4，所以末尾2位清零，得 0100 = 4，也就是说，

如果把3 按 4 对齐，那么所需内存的大小为 4，填充为1，结果完全正确。

那么清零操作除了连续的移位操作还有什么其他的操作呢？

我们在宏中看见的 &~ 连续的两个位运算，也能达到同样的效果。

我们可以带入具体数字计算一下，宏为 (((x)+(n)-1)&~((n) - 1) )

我们还是把3 按 4 对齐，宏变为(3 + 3)&~3，其中~3 = ~0011 = 1100，6 = 0110，6&~3 = 0110 & 1100 = 0100 = 4

结果正确。