关于位运算和一个求最小2次幂的算法

素颜马尾好姑娘i 2022-01-16 04:25 234阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

今天在HashMap的内部源码的时候，看到这样一个算法：

/**
     * Returns a power of two size for the given target capacity.
     * 返回大于或等于 cap 的最小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;
    }

第一眼看起来确实是一脸懵逼，通过只知道这是一个获取该数的**大于或等于 cap 的最小2次幂**，这么厉害，咋实现的呀？

**1、数据在内存中如何存储？**

我们知道"<<" 和 ">>" 分别代表 左移和右移位运算符号，表示 乘以2 和除以2（大多数时候适用），">>>"还是第一次见，这是代表什么意思呢？说到这里我们不得不去了解一下数据是如何存储在内存中的：

在32位的计算机系统中，int型数据占几个字节？ 4字节。其中每个字节有8个比特位，表示二进制位，位是计算机内部数据储存的最小单位。这是所有编程语言学习者都知道的。也就是说 int类型在内存中有4\*8 == 32个比特为 所以如果以整形数10为例，那么它在内存中完整存储的形式为：

> 00000000 00000000 00000000 00001010 ->对应 1x2^3+0x2^2+1x2^1+0x2^0 =10

那么int类型表示最大的数是不是就是:

> 11111111 11111111 11111111 11111111 ->对应 1x2^31+1x2^30...1x2^1+1x2^0

但为我们知道int类型的最大值为：2^31-1,显然上面的答案不是正确的。

这是因为在所有被int类型占用的比特位中，左起第一个位（即最高位）就是符号位。int类型的符号位上，0表示正数，1表示负数。在32位操作系统下，其余后面31位是数值位。也就是说：

> 11111111 11111111 11111111 11111111 所代表的数字为：1x2^**30**\+1x2^29...1x2^1+1x2^0 的相反数为：-(2^31-1)

这里需要注意的是，按原先的逻辑去理解的话

> 00000000 00000000 00000000 00000000 为+0

> 10000000 00000000 00000000 00000000 为-0

那他们表示的意义是一样的么？ 实际上，在32位系统下int类型中，我们计算机已经强行规定了这种情况，数字0采用“+0”的表示方法，即 00000000 00000000 00000000 00000000；而“-0”这个特殊的数字被定义为了-2^31。

因此我们看到32位系统下int类型的取值范围中，负数部分比正数部分多了一个数字，正数的最大取值是2^31-1，而负数的最小取值是-2^31。正数部分之所以要减去1，是因为被数字0占用了“+0”，而负数部分不需要用来表示0，因此原本的“-0”就用来表示-2^31这个数字。

**2、位运算如何进行？**

至此我们明白了数据在计算机中的存储形式，那位运算具体怎么运行的呢？ 以10和-10为例，其二进制完整表示为：00000000 00000000 00000000 00001010 和 10000000 00000000 00000000 00001010 为了便于观察，我们取后面8位：00001010

*  对于符号位移

例如将10的二进制向左移1位：那么变成 0001010 0 == 20 原先二进制数的第一位被移除，而最后一位被舍弃。将10的二进制向右移1位 原先二进制数最后一位被移除，第一位补0，则变成 000101 ==5

如将-10的二进制向左移1位， 10000000 00000000 00000000 00001010则变成：

> 10000000 00000000 00000000 0010100 为-20

如将-10的二进制向右移1位， 10000000 00000000 00000000 00001010则变成 ：

> 注意这里多了一个0-> 1 00000000 00000000 00000000 0000101 <-注意这里少了位

**也就是说符号移动，会保留原来的符号位，不会因为右移左移而带走符号位。**

*  对于无符号位移

**相反无符号位移会不关注符号位。** 例如将-10向右无符号右移就会变成：

> 010000000 00000000 00000000 0000101 变成了一个很大的正数了！！

如果将-10无符号左移，则变成：

> 00000000 00000000 00000000 00001010 = 20

但是！！并没有无符号左移动这样一件事情！ 跟右移运算不同的是，无符号左移和左移是一样的。因此java没有无符号左移运算。(<<<和<<<=将报错)

因为无符号右移运算需要考虑符号位的右移，而符号位只存在于二进制表示的最左边，最右边没有。所以不用区分无符号左移和左移运算。

**3、关于返回大于或等于 cap 的最小2次幂的算法**

我们以传入10为例子 ![a9a6035a8d949d27c7fdba39c694d9840c6.jpg][]

由这张图看起来，算法很容易懂了，其实最主要的是为了去让各个位从高到低 从0变成1或者维持1不变，这样就能找到该数最小的2次幂

> 另外，需要注意一下的是，第一步 int n = cap - 1; 这个操作，执行这个操作的主要原因是为了防止在cap已经是2的n次幂的情况下，经过运算后得到的结果是cap的二倍的结果，例如如果n为l6，经过一系列运算之后，得到的结果是0001 1111，此时最后一步n+1 执行之后，就会返回32，有兴趣的可以自己进行尝试；

小弟不才，如有问题，欢迎指出。

参考来源：

[https://blog.csdn.net/c10WTiybQ1Ye3/article/details/89411471][https_blog.csdn.net_c10WTiybQ1Ye3_article_details_89411471] [https://www.jianshu.com/p/927009730809][https_www.jianshu.com_p_927009730809]

转载于:https://my.oschina.net/617669559/blog/3043957

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/753e606ae8874b90ac4a2c7711f9c466.png
[a9a6035a8d949d27c7fdba39c694d9840c6.jpg]: /images/20220114/01f5d43843d0466c854a7e632944761f.png
[https_blog.csdn.net_c10WTiybQ1Ye3_article_details_89411471]: https://blog.csdn.net/c10WTiybQ1Ye3/article/details/89411471
[https_www.jianshu.com_p_927009730809]: https://www.jianshu.com/p/927009730809