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

时间:2022-12-29 05:11:08

如何判断一个非负整数是否是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: }
分类: 数据结构与算法