Power of Two
给定一个整数 n。如果 n 是 2 的幂，也就是说，对于某个非负整数 k ≥ 0，有 n = 2^k，则返回 true，否则返回 false。因此，1、2、4 和 8 符合条件，而 0、6 和所有负数都不符合。
函数
- ninteger
- 要测试的整数，可以是零或负数
- 返回值boolean
- true 表示当某个 k ≥ 0 时 n 等于 2^k，否则为 false
约束条件
-231 ≤ n ≤ 231-1
示例
- 输入
- n = 16
- 输出
- true
- 解释
- 16 = 2 × 2 × 2 × 2 = 2^4。用二进制表示是
10000，只有一个 1 位。
- 输入
- n = 24
- 输出
- false
- 解释
- 24 = 8 × 3。每次减半，得到 12、6，然后是 3。3 是奇数，但不是 1。24 的二进制表示是
11000，其中有两个 1 比特。
- 输入
- n = 1
- 输出
- true
- 解释
- 1 = 2^0，所以它是 2 的幂。它的二进制形式
1恰好有一个 1 位。
进阶
使用相同的位运算技巧，你能不使用循环，判断 n 是否是 4 的幂吗？
提示
逐个打开提示，每个都会多透露一点。
用二进制写出几个 2 的幂：
1、10、100、1000。它们有什么共同点，而 6（110）没有？2 的幂恰好有一个 1 位。比较二进制形式的
n和n-1：减去 1 会将最低位的 1 翻转为 0，并将它下面的每个 0 翻转为 1。所以，当
n是正数，并且它与n-1进行按位与运算的结果为 0 时，n就是 2 的幂。先检查符号，再检查位，因为 0 和负数永远不是 2 的幂。
题解
在二进制中，2 的幂是一个 1 位后面跟着若干个 0，例如 10000 表示 16。你可以不断将 n 除以 2，直到它变成奇数，以此确认这种形式；也可以用 n & (n-1) 一步完成，它会清除最低位的 1，只有当原来只有一个 1 时才会留下 0。先检查 0 和负数。
当数字为偶数时，除以 2
思路
将 2^k 除以 2，恰好除 k 次后会得到 1，而且过程中的每个值都是偶数。带有大于 1 的奇数因子的数，除到某个不为 1 的奇数时就无法继续减半。
在循环前，对 n ≤ 0 返回 false。没有任何 2 的幂是零或负数，而 0 是偶数，除以 2 后仍为 0，因此循环永远不会结束。每一步都会将 n 减半，所以 32 位输入最多需要 31 步。
算法
- 如果
n ≤ 0，返回 false。 - 当
n是偶数时，将它除以 2。 - 返回
n现在是否为 1。
def isPowerOfTwo(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1使用 n & (n-1) 清除最低位的 1
思路
减去 1 会把最低位的 1 变成 0，并把它下面的所有 0 变成 1，而更高位保持不变。2 的幂没有更高位：16 是 10000，15 是 01111，而 16 & 15 是 0。任何其他正数都有一个更高位的 1，同时出现在两个数中，因此按位与的结果不为 0。对于 24，你会得到 11000 & 10111，结果是 10000。
先检查 n > 0。0 & -1 是 0；在 32 位算术中，-2^31 是一个单独的 1 位，后面跟着 31 个 0，因此仅凭按位与会同时接受这两个数。整个测试只需要一次比较、一次减法和一次按位与。
算法
- 如果
n ≤ 0，返回 false。 - 计算
n & (n-1)，也就是清除n中最低位的 1 后得到的结果。 - 返回该结果是否为 0。
def isPowerOfTwo(n):
# One set bit: n - 1 flips it and every bit below, so the AND is 0.
return n > 0 and n & (n - 1) == 0
易错点和边界情况
- 跳过符号检查。0 会通过 AND 测试；对于 32 位整数，
-2^31也会通过，它只有一个 1 位。这两种情况都必须返回假。 - 对 0 执行减半循环。0 是偶数，减半后仍为 0，因此循环永远不会结束。
- 省略括号。
==的优先级高于&，因此在 C、C++ 和 JavaScript 中，n & n - 1 == 0表示n & ((n - 1) == 0)，不会报错，但会给出错误答案。应写成(n & (n - 1)) == 0。 - 使用对数。在双精度下，
log(536870912) / log(2)的结果是 29.000000000000004，因此整数检查会把2^29判为假。
常见问题3
如何检查一个数字是否是 2 的幂？
当 n > 0 且 n & (n-1) 等于 0 时，返回 true。2 的幂恰好有一个 1 位，而 n & (n-1) 会将它清除。如果不使用位运算，就在 n 为偶数时不断将它除以 2，并检查最终是否得到 1。
“2 的幂”的时间复杂度是多少？
n & (n-1) 检查的时间和空间复杂度都是 O(1)。折半循环的时间复杂度为 O(log n)，对于 32 位整数，最多需要 31 步。
1 是 2 的幂吗？0 呢？
1 是 2 的幂，因为 2^0 = 1。0 不是，因为没有整数次幂的结果是 0，而且它没有任何 1 位。负数也不是 2 的幂。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isPowerOfTwo(n):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
n = 16
预期输出
true