好用的算法技巧7、找出不大于N的最大的2的幂指数

传统的做法就是让 1 不断着乘以 2，代码如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13547.html

int findN(int N){
    int sum = 1;
   while(true){
        if(sum * 2 > N){
            return sum;
        }
        sum = sum * 2;
   }
}

这样做的话，时间复杂度是 O(logn)，那如果改成位运算，该怎么做呢？我刚才说了，如果要弄成位运算的方式，很多时候我们把某个数拆成二进制，然后看看有哪些发现。这里我举个例子吧。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13547.html

例如 N = 19，那么转换成二进制就是 00010011（这里为了方便，我采用8位的二进制来表示）。那么我们要找的数就是，把二进制中最左边的 1 保留，后面的 1 全部变为 0。即我们的目标数是 00010000。那么如何获得这个数呢？相应解法如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13547.html

1、找到最左边的 1，然后把它右边的所有 0 变成 1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13547.html

2、把得到的数值加 1，可以得到 00100000即 00011111 + 1 = 00100000。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13547.html

3、把 得到的 00100000 向右移动一位，即可得到 00010000，即 00100000 >> 1 = 00010000。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13547.html

那么问题来了，第一步中把最左边 1 中后面的 0 转化为 1 该怎么弄呢？我先给出代码再解释吧。下面这段代码就可以把最左边 1 中后面的 0 全部转化为 1，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13547.html

n |= n >> 1;
n |= n >> 2;
n |= n >> 4;

就是通过把 n 右移并且做或运算即可得到。我解释下吧，我们假设最左边的 1 处于二进制位中的第 k 位(从左往右数),那么把 n 右移一位之后，那么得到的结果中第 k+1 位也必定为 1,然后把 n 与右移后的结果做或运算，那么得到的结果中第 k 和 第 k + 1 位必定是 1;同样的道理，再次把 n 右移两位，那么得到的结果中第 k+2和第 k+3 位必定是 1,然后再次做或运算，那么就能得到第 k, k+1, k+2, k+3 都是 1，如此往复下去....文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13547.html

最终的代码如下文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13547.html

int findN(int n){
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
	n |= n >> 16;// 整型一般是 32 位，上面我是假设 8 位。
    return (n + 1) >> 1;
}

这种做法的时间复杂度近似 O(1)，重点是，高逼格。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13547.html

作者：帅地
来源：知乎文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13547.html