题目描述

设计一个算法，用于检测给定的整数n（n > 0）是否为2的幂。要求算法的时间复杂度为O(1)，即不依赖于输入n的大小。

解题思路

要检测一个数是否为2的幂，我们可以利用2的幂的一个特性：如果一个数是2的幂，那么它的二进制表示中只有一个1，其余位都是0。基于这个特性，我们可以通过位运算来检测。具体地，我们可以通过以下步骤判断：

1. 如果n小于等于0，则n不是2的幂。
2. 如果n和n-1进行按位与操作（n & (n-1)）的结果为0，则n是2的幂。这是因为如果n是2的幂，那么n的二进制形式为100...0（只有一个1），而n-1则为011...1（全为1，长度与n相同但少一位）。按位与操作会将两个数中对应的位都为1的位设为1，否则为0。因此，n & (n-1)的结果一定是0。

示例代码

PHP

function isPowerOfTwo($n) {
    if ($n <= 0) return false;
    return ($n & ($n - 1)) === 0;
}

// 测试
echo isPowerOfTwo(16) ? "true" : "false";  // 输出 true
echo isPowerOfTwo(3) ? "true" : "false";   // 输出 false

Python

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

# 测试
print(isPowerOfTwo(16))  # 输出 True
print(isPowerOfTwo(3))   # 输出 False

JavaScript

function isPowerOfTwo(n) {
    if (n <= 0) return false;
    return (n & (n - 1)) === 0;
}

// 测试
console.log(isPowerOfTwo(16));  // 输出 true
console.log(isPowerOfTwo(3));   // 输出 false

码小课相关内容分享

码小课网站中包含了大量关于算法和数据结构的详细讲解和示例代码，非常适合想要深入学习算法和编程的同学们。在码小课，你可以找到关于位运算、动态规划、搜索算法等多种算法思想的深入剖析，以及通过实际案例来加深理解。无论你是初学者还是希望进阶的开发者，都能在码小课找到适合自己的学习资源。