【优雅代码】05-从hashMap源码介绍位运算符
欢迎关注b站账号/公众号【六边形战士夏宁】，一个要把各项指标拉满的男人。该文章已在github目录收录。
屏幕前的大帅比和大漂亮如果有帮助到你的话请顺手点个赞、加个收藏这对我真的很重要。别下次一定了，都不关注上哪下次一定。
1.背景介绍
在看源码的时候往往会被位运算符劝退，但其实位运算符虽然难，但是用的时候使用规律/公式的。笔者以hashMap为例介绍位运算符
2.算数运算符
2.1.单目
- 负号运算符(-):就是负数
- 自增(++):++i表示先自己加1再赋值
- 自减(--):--i表示先自己先减1再赋值
2.2.双目
在A,B,n>0时,B为2^n可以使用其他操作符，但不要为了用而用，让代码变得难懂，除非做底层，否则不建议业务代码使用
- 加(+):四则运算加
- 减(-):四则运算减
- 乘(*):可用A << n,四则运算乘
- 除(/):A >> n,四则运算除
- 取余(%):A&(B-1)---->该方法只对2的N次方数系有效
2.3.三目
- a>b?true:false
3.关系运算符
- 等于符号(==):等于
- 不等于符号(!=):不等于
- 大于符号(>):大于
- 小于符号(<):小于
- 大于等于符号(>=):大于等于
- 小于等于符号(<=):小于等于
4.位与逻辑
4.1.位运算符
- 或(|):逐位比较两个操作数中只要有1个为1，结果为1，否则结果为0,得出最终结果
示例如下：x=(x<<1)|y其中x为位运算压缩空间的数值，左移一位方便将y值压入，因为只移了一位所以y只能为1或0，即x左移位数应于y的位数一致。此时因为y值前面都是0所以均取x原先值，到了y值得位置时反过来此时x该位置都补了0所以都取y的值，以此形成状态压缩 - 与(&):逐位比较两个操作数,两位同时为1，结果才为1，否则结果为0,得出最终结果。通常会用于高位清零的操作-> a&1 = 0 偶数
x&(x-1)=0 - 非(~):逐位自己的运算符，0则为1，1则为0,得出最终结果。
~x=-x-1 - 异或(^):逐位比较两个操作数，相同即为0，不同则为1。亦可称之为无进位相加。以动态规划算法，可以迅速判断是否仅仅是进行了交换，或者从偶数项里面找到唯一的奇数项等
(1)x^x=0
(2)xy=yx(交换律)
(3)(xy)z=x(yz)(结合律)
(4)xyy=x(自反性)->异或0就等于自己
(5)4k(4k+1)(4k+2)^(4k+3)=0
使用如下,有ab两个数:
a=a^b
b=b^a
a=a^b
则a和b的数字进行了交换。使用时注意内存地址需要不一样。
eor&(~eor+1)提取 的1,即某一位为1，左右两侧均为0 - 二进制状态压缩
|操作|运算|
|--|--|
|取出 n 的第 k 位|( n >> k ) & 1|
|取出 n 的后 k 位（ 0 ~ k-1 位）| n& ( ( 1 << k ) - 1 )|
|将第 k 位变为 1，赋值到 n | n|= ( 1 << k ) |
|将第 k 位变为 0，赋值到 n | n&= ( ~ ( 1 << k ) ) |
|找到最右侧的1 | N&((~N)+1) |
4.2.逻辑运算符
- 与(&&):数学上的交集
- 非(!):取反
- 或(||):数学上的并集
5.赋值
- 等于(=):将运算结果或者内存地址给到符号引用
- 加等于(+=)、减等于(-=)、乘等于(*=)、除等于(/=)、取余等于(%=):基本无应用场景、与等于(&=):基本无应用场景、异或等于(^=)、或等于(|=):基本无应用场景、左移等于(<< =):基本无应用场景、右移等于(>> =)
6.位移
- 带符号左移<<: x<<y 相当于x*(2y)--->此处的代表次方不是异或
- 带符号右移>>: x>>y 相当于x/(2y)--->此处的代表次方不是异或
- 无符号左移<<<
- 无符号右移>>>
7.二进制规律
A为任意数，B为2{n}，C为2{n+1}
- A/(2^{n})=A>>n
- A%B=A&(B-1)。取余的简写。原理如下，因为除以就是因为除以2^{n}就是右移n，即低位舍去，那么取余就是保留低位，高位舍去。而B-1就是低位1高位0。
- A%B=x,则A%C=x,或者A%C=x+B。====>如果A对C取余要么等于A对B取余，要么等于x+B。举例17%2==17%4==17%8==17%16==1==(17%32-16+1)。此处x=1。
- A%B=x,如果A&B=0，则A%C=x否则A%C=x+B。
8.编者注
以上个人认为比较重要的有如下
- 取余的变种按位与,即6.2
// 该段就是对hashMap的数组取余
if ((p = tab[i = (n - 1) & hash]) == null)
- 延伸规则，直接案例也是hashMap的高低位桶
// hashMap的获取hash值即原始值的哈希异或右移16次(高位变低位)，相互异或让结果变得更加随机
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// hashMap扩容代码片段，因为扩容是2倍，如果此时长度是2^{n}，扩容后就是2^{n+1}，根据6.3可知扩容后要么是原先位置要么是原先位置加2^{n}原先数组长度
// 循环分配片段，根据6.4可知如果A&B=0那么就分配在低位否则分配在高位
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
// 链表赋值给新数组片段，可知lo是旧位置，hi是新位置，和之前推论一致
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
- 位移符，一些coder喜欢秀操作会经常用，参考用例还是hashMap的默认容量
/**
* Returns a power of two size for the given target capacity.
*/
// 1+2+4+8+16 = 31覆盖全部32位，因为任何数最高位必然是1，右移1位再|运算自己就会导致第2位变成1。依次类推就会变成低位全是1的数+1变成2^n
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;
}
- 位运算符的常见规律，特别是状态压缩和二进制。算法中会遇到
9.位的基础知识
正数的原码，补码，反码都是一样的
负数的原码开头高为1其余一致，反码除开头不变其它取反，补码为反码的基础上加1
计算为补码相加
左移<<，左移1位则最左边的数丢弃，右边进一位0刚好是乘以2
正数右移则为补0
负数右移则为先转为补码高位补1，再得到源码
