黄阿信的个人博客

本文参考了哔哩哔哩UP主LH_Mouse的视频

前言

生活中我们可能经常遇到将给定的整数向上取整为最接近该数字的2次幂的情况，例如25的向上取整2次幂最接近该数字是32 = 2^5，37的向上取整2次幂最接近该数字是64 = 2^6，该算法也用很广泛的应用，例如伙伴系统和slab内存分配机制中，分配器在分配内存的时候，首先计算该次请求分配大小的向上取整2次幂，将该大小的空间返回，即假如请求8kb，则分配8kb大下的空间，假如请求分配9kb，则分配16kb的大小空间；又如，Java中的HashMap内部实际上是使用了数组，而且该数组的长度大小总是2^n，假如实例化HashMap的时候指定大小为length，那么实际上HashMap内部的数组大小就是length的向上取整2次幂。

算法讲解

解法一

利用一个变量，该变量从1不断地翻倍，假如该变量乘上2大于等于target，那么该变量的两倍即为所求：

    int test(int num) {
        if (num <= 1)return 1;
        int iteration = 1;
        while ((iteration << 1) < num){
            iteration <<= 1;
        }
        return iteration << 1;
    }

但是上面的算法时间复杂度是O(log(n))，下面介绍一种时间复杂度是O(1)的解法：

解法二

对于一般的数字，例如25，它的二进制是b011001，其向上取整为2次幂为32，对应的二进制为b100000，11对应的二进制数字为b01011，其向上取整为2次幂为16，对应的二进制为b10000，即对于非2^n的整数a，只需要将其二进制最左边的1取出来，再将该位置的右边全部替换为0，然后将该数字左移一位得到数字b，b就是a对应的向上取整为2次幂的数字。

所以关键就是如何将给定数字的最左边的1给提取出来，很容易想到的一个办法就是：不断地将该数字往右移，并记录下移动的次数，直到将该数字变为1：

    int test(int num) {
        if (num <= 1) return 1;
        int count = 0;
        while (num > 1) {
            num >>= 1;
            count++;
        }
        // 经过下面的处理，num 只保留了最左边的1
        num <<= count;
        //向上取2次幂
        return num << 1;
    }

但是很遗憾，上面的时间复杂度是仍然是O(log(n))，而且部分答案不正确，如8对应的解是16（当然了，这种错误想要避免也很容易）。

我们再想想，由25 = b011001到32 = b100000，不一定要“将最左边的1提取出来，然后该位置的右边全部赋值为0，再将数字往左移一位”这种方法，也可以将25的二进制数中，找出第一个1的位置，然后将该位置的右边全部置为1，即b011111，然后将得到的数字加1，得到b100000，该数字不就是所求吗？

关键步骤就变成了怎么将给定数字的最高有效位的右边全部置为1（包含该位置），这里我们可以从算术右移中找到灵感，算数右移就是符号位跟着移动，并且符号位跟原来的符号位一致；

假如给定数字是001xxxxx，那么该怎么变成0011xxxx？借助移位操作和或运算即可

a = 001xxxxx
b = 0001xxxx
c = a | b
  = 0011xxxx

由0011xxxx又该怎么变成001111xx？还是借助移位操作和或运算即可

a = 0011xxxx
b = 000011xx
c = a | b
  = 001111xx

……

但是我们什么时候结束上面的操作？请注意我们的int类型是32位字长，为了确保所有的正整数都可以被考虑到，如某个整数0x20000001，我们需要将最左边的1移动29次，我们只需要将num右移16位，然后再异或一次，将得到32个“1”（当然了，末尾的几个1会被舍弃）然后该算法如下：

    int test(int num) {
        if (num <= 1) return 1;
        num |= num >> 1;
        num |= num >> 2;
        num |= num >> 4;
        num |= num >> 8;
        num |= num >> 16;
        return num + 1;
    }

但是前文说到，当给定的数字本身就是符合2^n，该算法返回的是2^(n + 1)，所有我们在算法的开始前要先判断一下给定数字是不是2的次幂，如果一个数字是2的次幂，那么它的二进制一定是n = 00……10000……0，该数字减一后一定是n - 1 = 00……01111……1，这二者进行与运输后结果为0，根据这个即可判断给定数字是不是2的次幂，改进后的算法如下：

    int test(int num) {
        if (num <= 0) return 1;
        if ((num & (num - 1)) == 0) return num;
        num |= num >> 1;
        num |= num >> 2;
        num |= num >> 4;
        num |= num >> 8;
        num |= num >> 16;
        return num + 1;
    }

将正整数向上取整为2次幂

前言

算法讲解

解法一

解法二