将一个32位整数圆整到不小于它的2的整数次幂

DevLabs Post in C语言
0

代码来自: http://blog.codingnow.com/cloud/CodeCollection

实现很巧妙, 原理也很简单, 只要展开为二进制, 跟着程序逻辑走一遍就可以看明白了.

 

代码:

 

static inline bool is_pow_of_2(uint32_t x)
{
return !(x & (x-1));
}

static inline uint32_t next_pow_of_2(uint32_t x)
{
if (is_pow_of_2(x))
return x;

x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;

return x + 1;
}

 

如果一个数是二的整数次幂的话, 那么它正好就是二进制的位权. 也就是说, 如果将这个数展开为二进制表示, 那么这一串二进制数中只有一位为1, 其余的都为0.
如果将此数减一, 那么本来一1的这一位将变成0, 这一位以下的位将全部变成1.
比如: 8 = 0000 1000
7 = 0000 0111
那么is_pow_of_2()就很好理解了, 只有当这个数为二的整数次幂时, x & x – 1 才会为0.

至于next_pow_of_2()这个函数,  在个语句下面打印出它的二进制展开, 就可以看出原理来了:

这里是对4097进行圆整的过程:

res

« Prev: :Next »

Leave a Reply