linux内核中SH_DIV宏分析

在读linux内核中关于时钟部分的代码时，遇到了一个叫SH_DIV的宏，它包含的
技巧颇为有趣。自己写代码时可能用得到。

下面是这个宏的注释和定义：

/* Suppose we want to devide two numbers NOM and DEN: NOM/DEN, the we can
 * improve accuracy by shifting LSH bits, hence calculating:
 *     (NOM << LSH) / DEN
 * This however means trouble for large NOM, because (NOM << LSH) may no
 * longer fit in 32 bits. The following way of calculating this gives us
 * some slack, under the following conditions:
 *   - (NOM / DEN) fits in (32 - LSH) bits.
 *   - (NOM % DEN) fits in (32 - LSH) bits.
 */
#define SH_DIV(NOM,DEN,LSH) (   (((NOM) / (DEN)) << (LSH))              \
                             + ((((NOM) % (DEN)) << (LSH)) + (DEN) / 2) / (DEN))


计算 (N << L) / D，可以等价于下面的算式：
(N / D) << L + ( (N % D) << L + (D / 2) ) / D

下面是推导过程：

N = (N / D) * D + (N % D)

N << L = N * 2^L
       = ( (N / D) * D + (N % D) ) * 2^L
       = (N / D) * D * 2^L + (N % D) * 2^L

(N << L) / D = ( (N / D) * D * 2^L + (N % D) * 2^L ) / D
             = ( (N / D) * D * 2^L ) / D + ( (N % D) * 2^L ) / D
         = (N / D) * 2^L + ( (N % D) * 2^L ) / D
         = (N / D) << L + ( (N % D) << L ) / D

这时与最终的等式只差一个(D / 2)，当在C语言中进行除法运算(N / D)时，结
果总是向下取整，余数部分全都被舍去了，因此，在计算除法前给被除数加上除
数的一半，可以起到四舍五入的效果，即：(N + (D / 2)) / D。
所以，在前面推导过程的最后一步时，在除以D前要加上(D / 2)，即：
(N << L) / D = (N / D) << L + ( (N % D) << L + (D / 2) ) / D