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

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

今天在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为例子

由这张图看起来,算法很容易懂了,其实最主要的是为了去让各个位从高到低 从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://www.jianshu.com/p/927009730809

# 算法

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×