【算法题】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));}
}