给定一个正整型数值，如何获取该数下一个2的n次幂值

港控/mmm° 2022-01-20 10:01 148阅读 0赞

## 问题解读 ##

题目的意思就是获取某个数的下一个2的n次幂，比如说输入5，2的2次幂是4，2的3次幂是8，所以应该输出 **8**

咦，怎么有一股似曾相识的感觉呢？如果有研究过HashMap源码的同学应该会知道，HashMap底层数组长度不就是2的n次方吗，那HashMap是不是就会有这道题的答案呢？

答案是肯定的，HashMap中确实就有这个方法，而且实现上非常巧妙与简洁，下面让我们来看看这道题的标准答案吧！

首先我们来看看他的源码

位于HashMap中的

tableSizeFor(int cap)
    复制代码

方法中

static final int tableSizeFor(int cap) {
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    复制代码

对位运算不是特别熟悉的同学，初次看到这段代码可能会有点懵，下面让我们来慢慢解读一下这段代码，解读之前，我们需要先了解一下位运算是什么东西，以及上面代码出现的位运算符是干什么的。

#### 十进制与二进制 ####

在生活中，我们所看到的数字几乎全都是十进制的数字，但是在计算机底层中存储的以及它能识别的数字都是二进制的，而位运算就是直接对整数在内存中的二进制位进行操作的运算，对比十进制的运算，它的速度更加快。

二进制与十进制可以相互转化，例如：

十进制     二进制
    2           10
    3           11
    4           100
    5           101
    6           110
    7           111
    8           1000
    复制代码

具体转换公式可访问 [百度百科（点我）][Link 1]

#### 位运算符 ####

位运算符就是直接操作二进制数的运算符

分别有：**按位与、按位或、按位异或、按位取反、左移、带符号右移、无符号右移** 具体释义可参考[这篇文章][Link 2]

这里解释一下上面代码出现的两个位操作

1.  **|=**

|=的意思就是或等于，跟+=差不多

a|=b 等价于 a=a|b
    复制代码

而 **|** 这个符号则是按位或：将两数转换成二进制，对比同位上元素，同位上只要有一个1或者全都是1，那结果就是1，否则就是0

举个例子：

int a = 8 | 7
    转换成二进制
    8：   1 0 0 0 
    7：     1 1 1
    -------------
    结果：1 1 1 1
    而1111转换成十进制的话那就是15
    所以a=15
    复制代码

1.  **>>>** 无符号右移

将数值转换成二进制后向右移动n位

例如：

int a  = 8 >>> 2
    8转换为二进制就是 
    1 0 0 0
    向右移动两位变成
        1 0
    所以a = 2
    复制代码

## 原代码解析 ##

static final int tableSizeFor(int cap) {
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    ｝
    复制代码

通过对十进制进行二进制转换后，我们可以发现一个规律，那就是2的n次幂的二进制数，除了首位是1，其他位都是0，比如说2的1次幂是10、2的2次幂是100、2的3次幂是1000， 所以

**假如我们要得到一个数的下一个2的n次幂，那么需要将这个数转换成2进制之后，把它的所有位上的数值都变成1，最后加1，就能够得到这个数的下一个2的n次幂了**

举个例子，我们要获取6的下一个n次幂

原数：6
    1.转换成二进制：110
    2.把它的所有位变成1：111
    3.加一使其进位：1000
    4.转换成十进制：8
    复制代码

所以就上面源码的步骤就可以解析为

//把数无符号右移一位后，与原数按位或，这样可以保证这个数的最高位与次高位是1
           n |= n >>> 1;
           // 由于这个数的最高位与次高位已经是1了，所以这次向右移动两位并按位或，使前四位都是1
            n |= n >>> 2;
            // 使从最高位数，前八位变成1
            n |= n >>> 4;
            // 同理，使前十六位变成1
            n |= n >>> 8;
            // 因为int最高只有32位 ，所以到这里就可以确定这个数的所有位都是1了，
            n |= n >>> 16;
            // 加一则所有1位向前进一位变成0，即是2的n次幂
            n+1
    复制代码

至此，这个问题的就已经解读得差不多了

## 问题引申 ##

HashMap里面数组的长度为什么总是2的n次幂？

因为HashMap是一个用来存储key-value的一个集合，它的底层是数组+链表+红黑树。

当向HashMap中添加元素的时候，它需要对key进行hash计算得到hash，然后根据数组的长度对hash进行取模，得到这个元素应该存放在这个数组的哪个位置上，也就是说要进行 **hash % n** 这个操作，而这个操作是比较消耗性能的，所以我们能不能将这个操作转换成位运算，以此避免无谓的性能损耗呢?

答案是有的：当被余数是2的n次幂时

**（n-1）& hash等价于hash % n**

具体解析可看这篇文章 [由HashMap哈希算法引出的求余%和与运算&转换问题][HashMap]

[Link 1]: https://link.juejin.im?target=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E5%258D%2581%25E8%25BF%259B%25E5%2588%25B6%25E8%25BD%25AC%25E4%25BA%258C%25E8%25BF%259B%25E5%2588%25B6%2F393189%3Ffr%3Daladdin
[Link 2]: https://link.juejin.im?target=https%3A%2F%2Fbaike.baidu.com%2Fitem%2F%25E4%25BD%258D%25E8%25BF%2590%25E7%25AE%2597%2F6888804%3Ffr%3Daladdin
[HashMap]: https://link.juejin.im?target=https%3A%2F%2Fwww.cnblogs.com%2Fysocean%2Fp%2F9054804.html