如何判断一个数是否为2的幂次方

题目描述
给定一个整数n，判断它是否是2的幂次方。如果是，返回true；否则返回false。2的幂次方指的是形如2^k（k为非负整数）的数，例如1（2^0）、2（2^1）、4（2^2）、8（2^3）等。

解题过程

1. 理解2的幂次方的二进制特征
   在二进制表示中，2的幂次方数有一个关键特征：其二进制形式仅包含一个"1"，且其余位均为"0"。例如：

   • 1的二进制：0001（仅第0位为1）
   • 2的二进制：0010（仅第1位为1）
   • 4的二进制：0100（仅第2位为1）
   • 8的二进制：1000（仅第3位为1）
     这一特征是所有解法的核心依据。

2. 基础解法：循环除以2

   • 步骤：
     1. 若n ≤ 0，直接返回false（2的幂次方必须是正数）。
     2. 当n > 1时，重复以下操作：
        • 若n除以2的余数不为0，说明n不是2的幂次方，返回false。
        • 否则，将n更新为n/2。
     3. 循环结束后，说明n最终变为1，返回true。
   • 时间复杂度：O(log n)，空间复杂度O(1)。
   • 示例：n=8 → 8÷2=4 → 4÷2=2 → 2÷2=1 → 返回true。

3. 位运算解法：利用n & (n-1)

   • 原理：
     • 对于任意2的幂次方n，其二进制形式为"10...0"，则n-1的二进制形式为"01...1"。
     • 将n与n-1进行按位与操作（&），结果必为0。例如n=8（1000），n-1=7（0111），1000 & 0111 = 0000。
     • 若n不是2的幂次方（如n=6，二进制110），n-1=5（101），110 & 101 = 100 ≠ 0。
   • 步骤：
     1. 若n ≤ 0，返回false。
     2. 计算n & (n-1)，若结果为0，返回true；否则返回false。
   • 时间复杂度：O(1)，仅需一次位运算。
   • 注意：需单独处理n=0的情况，因为0 & (-1) 可能引发未定义行为（实际中0-1=-1，需避免）。

4. 位运算解法：利用n & (-n)

   • 原理：
     • 负数在计算机中以补码形式表示，-n等于n的二进制取反后加1。
     • 对于2的幂次方n，其二进制仅最高位为1，-n会保留该位，其余位取反后加1，最终n & (-n)的结果等于n本身。例如n=8（1000），-n=-8（补码为1000），1000 & 1000 = 1000 = 8。
     • 若n不是2的幂次方（如n=6，二进制110），-n=-6（补码为1010），110 & 1010 = 0010 ≠ 6。
   • 步骤：
     1. 若n ≤ 0，返回false。
     2. 计算n & (-n)，若结果等于n，返回true；否则返回false。
   • 时间复杂度：O(1)，同样仅需一次位运算。

5. 边界情况与优化

   • 处理n=0：所有解法均需先排除n≤0的情况，因为0和负数不是2的幂次方。
   • 推荐解法：n & (n-1)解法最简洁高效，且易于理解，是面试中的常见答案。

总结
判断2的幂次方的核心是利用其二进制特征。优先掌握n & (n-1)的位运算解法，它既高效又直观，适用于大多数编程语言。