【算法题】2 的 n 次幂的背后
前言： 说实话，真的不爱写算法题相关的文章了，觉得没啥意义，但是对这种比较好玩并且简单，学会了就能很好提高算法效率的文章，还是要写一写，不哭不哭，你不会不是你的错，只是因为你懒，学会了就好了，加油！！
一、2 的 n 次幂的特点
我们先看看 2 的 n 次幂都有什么 ？
| n | 2 的 n 次幂 | 二进制表示 |
|---|---|---|
| 1 | 2 | 10 |
| 2 | 4 | 100 |
| 3 | 8 | 1000 |
| 4 | 16 | 10000 |
| … | … | … |
通过观察，我们可以得出，2 的 n 次幂的二进制表示只有最高位是 1， 其余位都是 0，这也是 2 的 n 次幂的特点 。
二、如何判断某个数 x 是否是 2 的 n 次幂
1. 暴力法
对 x 一直除 2 取余数 % ， 看看最后当 x == 0 时，余数是否为 0 ，若是为 0 ，说明其是 2 的 n 次幂
2. 利用 2 的 n 次幂的二进制特点
2 的 n 次幂的二进制表示只有最高位为 1，其余位都为 0。因此，我们对其减 1 得到的结果的二进制表示只有原二进制最高位为 0， 其余位都为 1。如下表所示：
| n | 2 的 n 次幂 （x） | 二进制表示 | (x-1) 的二进制表示 | x & (x-1) |
|---|---|---|---|---|
| 1 | 2 | 10 | 01 | 0 |
| 2 | 4 | 100 | 011 | 0 |
| 3 | 8 | 1000 | 0111 | 0 |
| 4 | 16 | 10000 | 01111 | 0 |
| … | … | … | … | 0 |
因此，我们将 该数字 x 按位与 (x - 1)，若是结果为 0 ，说明该数字是 2 的 n 次幂
Java 代码表示如下：
if((x & (x-1)) == 0){// 说明是 2 的幂次return true;}
三、如何找到距离某个数最近的 2 的 n 次幂
1. 暴力法
排除 ， 我们就不使用暴力法，就不用，就不用 ~~
2. 重点：以数字的二进制形式进行思考
以数字 5 为例，距离它最近的2的幂次，比5大的有一个，比5小的有一个，5 的二进制表示为 101。
因为 2 的幂次只有最高位为 1，那么问题的关键就在于如何消除最低位的 1，消除的方法为 加上最低位 1xx(xx位置为 k 个 0) ，或者减去最低位的 1xx(xx位置为 k 个 0) 。
我们不断进行消除，最后就一定能得到距离 x 的最近的两个 2 的幂次
得到数字 x 的最低位 1xx(xx位置为 k 个 0) 的方法为 ： x & (-x)
理解 x & (-x) 之前，我们先恶补一下计算机基础知识：
以 -5 为例：
1. 把这个负数的绝对值转换为二进制，即求原码 （101）
2. 把原码取反，即求反码 （11111111111111111111111111111010）
3. 把反码加1，即求补码 （11111111111111111111111111111011）
所以， 5 & -5 = 1
解释： 通过上述变化 -5 只有最低位的 1xx(xx位置为 k 个 0) 和 5相同，其余位都变得和 5 不同（即被取反了）
3. 寻找最近位置完整代码
// 得到小于 n 的距离 n 最近的 2 的幂次public int getMinDistance(int n){// 直接就是 2 的 n 次幂if((n & (n - 1)) == 0){return n;}// 最低位的 1int lb = n & (-n);// 我们要通过不断加上减去最低位1，来消除低位的1，从而得到只有最高位为1的2的幂次// 但是我们要的是距离n最近的小于n的幂次，因此取两者的最小值return Math.min(getMinDistance(n + lb), getMinDistance(n - lb));}// 得到大于 n 的距离 n 最近的 2 的幂次public int getMaxDistance(int n){// 直接就是 2 的 n 次幂if((n & (n - 1)) == 0){return n;}// 最低位的 1int lb = n & (-n);// 我们要通过不断加上减去最低位1，来消除低位的1，从而得到只有最高位为1的2的幂次// 但是我们要的是距离n最近的大于n的幂次，因此取两者的最大值return Math.max(getMinDistance(n + lb), getMinDistance(n - lb));}
我们在对上面代码得到的结果，进行一个距离绝对值的判断，就能得到我们要的结果了
纠错： 需要这么绕嘛？
当然不需要，在实际实现时，我们只需要找到 x 的最高位 1 的位置，然后进行两次 1 的左移操作就行了。 （以 5 为例子， 1 << 2 (距离最近的小于 5 的位置)，1 << 3 (距离最近的大于 5 的位置)）
为了下一道题铺垫才这么做的 （试图为自己被绕进去了找借口，wwwww）
四、如何通过不断加减 2 的 n 次幂使得某个数最终结果为 0，最少操作次数
通过上面的分析，我们可以轻松得出这道综合题的完整代码，如下：
class Solution {// 6365. 将整数减少到零需要的最少操作数// 操作依据 —— 找到距离目标值最近的2的n次幂public int minOperations(int n) {return dfs(n);}public int dfs(int n){// 说明是 2 的幂次if((n & (n-1)) == 0){// 说明是 2 的幂次,最后再处理一次，即减去这个数字return 1;}int lb = n & (-n);// 操作次数 + 1，然后递归得到的新的数字return 1 + Math.min(dfs(n + lb), dfs(n - lb));}
}