判断一个整数是否是2的幂次方 - 算法解析

判断一个整数是否是2的幂次方

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例1: 输入: 1 输出: true 解释: 2^0= 1

示例 2: 输入: 16 输出: true 解释: 2^4= 16

示例 3: 输入: 218 输出: false

解题思路

如果一个数是2的幂次方，那么它的二进制表示中只有一个1，其余位都是0。

我们可以通过位运算来判断一个数的二进制表示中是否只有一个1。

首先，我们可以使用 n & (n-1) 来去除 n 的二进制表示中最右边的1。

如果 n 是2的幂次方，那么经过这个运算后，n 的二进制表示中只有一个1，其余位都是0。

然后，我们可以判断 n 是否等于0。

如果等于0，表示 n 的二进制表示中只有一个1，返回 true； 如果不等于0，表示 n 的二进制表示中还有其他位不为0，返回 false。

代码示例:

def is_power_of_two(n):
    if n <= 0:
        return False
    return (n & (n - 1)) == 0

解释:

• 当 n <= 0 时，直接返回 False，因为0和负数都不是2的幂次方。
• 使用 n & (n - 1) 来判断 n 的二进制表示中是否只有一个1。
• 如果 n & (n - 1) == 0，则表示 n 的二进制表示中只有一个1，返回 True。
• 否则，返回 False。

总结:

通过位运算，我们可以高效地判断一个整数是否是2的幂次方。该方法简单易懂，效率高，适用于各种编程语言。