LeetCode笔记：2 的幂
问题
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
示例 1：
输入： n = 1
输出： true
解释： 20 = 1
示例 2：
输入： n = 16
输出： true
解释： 24 = 16
示例 3：
输入： n = 3
输出： false
示例 4：
输入： n = 4
输出： true
示例 5：
输入： n = 5
输出： false
提示：
- -231 <= n <= 231 - 1
进阶： 你能够不使用循环/递归解决此问题吗？
解法一
思路：
常规思路，一个数字可以拆为许多个 2 相乘得到，那么我们将这个数字不断的除以 2，如果结果输出 1，那么就是 2 的幂。
代码：
/**
* @param {number} n
* @return {boolean}
*/
var isPowerOfTwo = function (n) {
// 两种特殊数字先处理
if (n === 1) return true;
if (n === 0) return false;
// 调用方法处理其他数字
return divide(n);
// 递归查找
function divide(num) {
const result = num / 2;
const remainder = num % 2;
if (remainder !== 0) {
// 余数不为0时候，表明这个数字不能被2整除，直接淘汰
return false;
} else if (result === 1) {
// 余数为0的情况下，得到最终结果为1，就是合格的数字
return true;
} else {
// 余数为0的情况下，结果值大于等于2，表明还可以继续除以2，递归循环
return divide(result);
}
}
};
解法二
思路：
直接处理二进制，如果n是 2 的幂，则有如下规则：
n在二进制表示中是只有一个 1，其余都是 0n - 1就是将n中的那个 1 变为 0，后面的数字变为 1- 我们使用按位与
&的特性，得到n & (n - 1)总是 0
如果还有疑惑，我们来详细解释一下这个过程
我们复习下按位与 & 的特性，两个数都是 1 结果为 1，否则为 0，如下：
| a | b | a AND b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
n & (n - 1)转化的原理如下,假设 num = 8：
8 的二进制表示中，1 在最左边
8 (1 0 0 0)
7 (0 1 1 1)
8 & 7 (0 0 0 0)
▲
我们可以看到第一位的 1 转化为了 0，结果是全部为 0。
复制以下代码到控制台可以看到打印结果：
console.log((8).toString(2)); // 输出：1000
console.log((7).toString(2)); // 输出：111
console.log((8 & 7).toString(2)); // 输出：0（唯一的1转化为了0）
结论：
n & (n - 1)可以将n二进制数字最右边的 1 转化为 0，在我们这个问题里，唯一的一个 1 就被转化为了 0
同样使用按位与的案例，参考 汉明距离
代码：
/**
* @param {number} n
* @return {boolean}
*/
var isPowerOfTwo = function (n) {
return n > 0 && (n & (n - 1)) === 0;
};
解法三
思路：
仍然是直接处理二进制，这次的计算方法稍有不同，运用二进制负数的特性，n & -n来计算。
计算之前，我们了解下如何计算二进制的负数值。在计算机中，负数以其原正数的补码形式表达。什么是补码？
原二进制按位取反得到反码，反码+1 即得到补码。
简单来说，负数的二进制值，是根据原来的正数的二进制值，取反码+1 得到。
举个例子，n & -n转化的原理如下,假设 num = 8：
8 (1 0 0 0)
8的反码 (0 1 1 1)
8的反码+1
8的补码
-8 (1 1 1 1)
8 & -8 (1 0 0 0)
▲
我们可以得出规律，只要满足(n & -n) === n条件的数字，就是 2 的幂。
代码：
/**
* @param {number} n
* @return {boolean}
*/
var isPowerOfTwo = function (n) {
return n > 0 && (n & -n) === n;
};
评论