要么改变世界,要么适应世界

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

2020-08-11 20:49:00
126
目录

本文参考了哔哩哔哩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,然后将该数字左移一位得到数字bb就是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 = b01100132 = 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;
    }
历史评论
开始评论