请用python代码写出判断一个数是不是2的N次方,并解释算法原理
时间: 2024-02-24 19:53:26 浏览: 104
以下是 Python 代码实现:
```python
def is_power_of_2(n):
"""判断一个数是不是2的N次方"""
if n <= 0:
return False
return n & (n - 1) == 0
```
这里使用了位运算的方法来判断一个数是否是2的N次方。它的原理是,一个数如果是2的N次方,那么它的二进制表示中只有最高位是1,其余位都是0。例如,4的二进制表示是100,8的二进制表示是1000,16的二进制表示是10000。
而一个数减去1后,它的二进制表示中最高位变成了0,后面的所有位都变成了1。例如,3的二进制表示是11,3-1=2的二进制表示是10;7的二进制表示是111,7-1=6的二进制表示是110。
如果我们把一个2的N次方的数(例如4)和它减去1的结果(例如3)进行按位与运算,得到的结果就是0。例如:
```
4: 100
3: 011
& --------
000
```
而如果一个数不是2的N次方,那么它的二进制表示中就不只最高位是1了。例如,5的二进制表示是101,7的二进制表示是111。这些数减去1之后,它们的二进制表示中最高位变成了0,后面的所有位都变成了1。例如,4的二进制表示是100,4-1=3的二进制表示是011;8的二进制表示是1000,8-1=7的二进制表示是0111。如果我们把这些数跟它们减去1的结果进行按位与运算,得到的结果就不是0了,例如:
```
5: 101
4: 100
& --------
100
7: 111
6: 110
& --------
110
```
因此,我们可以通过这种方法来判断一个数是否是2的N次方。具体实现中,我们先判断这个数是否是正整数,如果是负数或0,就直接返回False。然后我们把这个数和它减去1的结果进行按位与运算,如果结果是0,就说明这个数是2的N次方,返回True;否则返回False。
阅读全文