如何判断一个非负整数是否是2的幂

如何判断一个非负整数是否是2的幂

如何判断一个数是2的幂，主要是要找出2的幂次方的数的特点。我们知道，1个数乘以2就是将该数左移1位，而2的0次幂为1， 所以2的n次幂（就是2的0次幂n次乘以2）就是将1左移n位， 这样我们知道如果一个数n是2的幂，则其只有首位为1，其后若干个0，必然有n & (n - 1)为0。（在求1个数的二进制表示中1的个数的时候说过，n&(n-1)去掉n的最后一个1）。因此，判断一个数n是否为2的幂，只需要判断n&(n-1)是否为0即可。

实现：

   1: bool powerof2(unsigned int n)

   2: {

   3:     return ((n & (n -1)) == 0);

   4: }

分类: 数据结构与算法