469，位运算求最小的2的n次方

Original 山大王wld 数据结构和算法 2022-05-19

收录于合集 #算法图文分析 161个

Promise yourself to be so strong that nothing can disturb your peace of mind.

答应自己要坚强，不让任何事物烦扰内心的平静。

问题描述

给一个函数f(x)，返回一个不小于x的最小的2的n次方。描述的比较绕口，举个例子。

f(7)=8
f(9)=16
f(30)=32
f(64)=64

注意：

x是正整数
0<x<Integer.MAX_VALUE

循环解决

我们看到返回的结果都是2的n次方，并且是不小于x的最小的2的n次方。如果把2的n次方转换成二进制我们就会发现，只有一个位上是1，其他位上全部是0，随便举几个数字看一下

所以最简单的一种方式就是通过循环来计算，先用x和1比较，如果大于1，那么1就往左移一位，继续比较……，一直这样下去，直到不小于为止，原理比较简单，来看下代码

1public int lowPower(int x) {
2    int n = 1;
3    while (x > n)
4        n <<= 1;
5    return n;
6}

代码非常简洁，基本没什么难度

位运算解决

再来看下位运算，我们随便举个例子，比如53，他的二进制位如下，如果要找到不小于53的最小的2的n次方，我们只需要把53的二进制位中最左边的1往左移一位，其他的全部变为0即可。

所以一种最简单的方式就是通过移位运算，把53最左边的1全部往右边铺开，就变成了00111111，然后再加1就变成了了01000000。最后来看下代码

 1public int lowPower(int x) {
 2    //这里把最左边的1全部往右边铺开
 3    x |= x >>> 1;
 4    x |= x >>> 2;
 5    x |= x >>> 4;
 6    x |= x >>> 8;
 7    x |= x >>> 16;
 8    //最后再加1返回
 9    return x + 1;
10}

但是这里有个小问题就是，如果x本来就是2的n次方，比如x是16，运算的结果就会变成32，与我们实际要求不符。所以这里我们可以先让x-1，然后再进行运算，所以正确答案应该是下面这样

 1public int lowPower(int x) {
 2    //这里把最左边的1全部往右边铺开
 3    //x--;
 4    x -= 1;
 5    x |= x >>> 1;
 6    x |= x >>> 2;
 7    x |= x >>> 4;
 8    x |= x >>> 8;
 9    x |= x >>> 16;
10    //最后再加1返回
11    return x + 1;
12}

或者也可以改成这样，当然没有上面的代码简洁

 1public int lowPower(int x) {
 2    if (x == 1)
 3        return 1;
 4    //这里把最左边的1全部往右边铺开
 5    x -= 1;
 6    x |= x >>> 1;
 7    x |= x >>> 2;
 8    x |= x >>> 4;
 9    x |= x >>> 8;
10    x |= x >>> 16;
11    //执行完下面这行代码，x相当于把
12    //后面的1全部减掉了，只留下最前
13    //面的那个1，也是2的n次方，
14    //只不过这个是小于原来x的最大的
15    //2的n次方
16    x -= x >> 1;
17    //然后我们再把它往左移一位，就变
18    //成了不小于原来x的最小的2的n次方
19    return x << 1;
20}