有用的算法技巧 7. 求不大于N的2的最大幂指数

7. 求不大于N的2的最大幂指数

传统方法是1乘2，代码如下：

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

如果这样做的话，时间复杂度是O(logn)。那么如果改成按位运算呢？正如我刚才所说，如果我们想使用按位运算，很多时候我们会将一个特定的数字分解为二进制，然后看看我们发现了什么。我在这里给你举个例子。

例如N=19，所以转换成二进制就是00010011（为了方便我用8位二进制来表示）。所以我们要找的数字就是保留 最左边的一个二进制，并将后面的所有 1 都改为 0。也就是说，我们的目标数字是 00010000。那么我们如何把这个说出来呢？相应的解如下：

1。找到最左边的1，然后把它右边的0全部改成1

2。所得值加 1 即可得到 00100000，即 00011111 + 1 = 00100000。

3.将得到的00100000向右移动一位，得到00010000，即00100000 >> 1 = 00010000。

那么问题是第一步如何将最左边末尾的0转换为1呢？首先让我给你代码，然后解释。下面的代码可以将最左边的1末尾的所有0全部转换为1。将n向右移动，进行或运算即可得到

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

。解释一下，我们假设最左边的是二进制数的第k位（从左到右数），所以n右移一位后，结果中的第k+1位也一定是1 ，然后将n与右移后的结果进行或运算，则得到的结果中的第k位和第k+1位必须为1；类似地，如果n再右移两位，那么得到的结果+2和k+3位中的第k位一定为1，然后再次进行或运算，则可以得到第k，k+ 1、k+2、k+3 都为 1，以此类推......

最终代码如下

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) 。关键是高清。

作者：帅迪
来源：知乎