将一个数上调至2^n的倍数《参考STL源码》

    最近在看STL源码剖析这本书,这本书分析的对象是SGI STL。在讲述第二级配置器的实现内容时,有这么一段代码:

         enum {__ALIGN=8};

         size_t ROUND_UP(size_t bytes)   //将bytes上调至8的倍数

         { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN – 1)); }

         毫无疑问,这段代码是非常高效的。仔细分析一下,就会发现这段代码适合用来将所有数上调至2^n的倍数:一个数k如果正好是2^n的倍数,那么用二进制来 表示的话,低n位必定全是0,而 _ALIGN-1的二进制表示则是低n位全为1,那么k+ _ALIGN-1和~(_ALIGN – 1)取与必定是k本身;如果一个数k不是2^n的倍数,则必有m*2^n<k<(m+1)*2^n,我们要做的就是求出(m+1)*2^n, 则k用二进制来表示的话,低n位肯定不全为0,再加上_ALIGN-1必然会向第n+1位进位,此时若将低n位全部置零的话,得到刚好就是 (m+1)*2^n,而和~(_ALIGN – 1)取与正好达到这一效果。

        这里的关键在于,对一个数如果有m*2^n<k<(m+1)*2^n,那么有 k=m*2^n+p, 且p<2^n,这样k就分成了两部分,在用二进制表示的时候,p是存储在低n位中,而m*2^n是存储在高位中(即除去低n位的剩余位数),P+ALIGN-1,肯定向高位进一,即为(m+1)*2^n+P1,然后与全0,则得到(m+1)*2^n=2^(n+1)。

本文版权归作者 kanego 和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利.
原文地址:https://www.cnblogs.com/kanego/p/2465447.html