移位运算
有符号左移：<<
左移1位相当于乘2，x << n等价于x * (2 ^ n)。
int i = 4;
i = i << 2; //= 4 * (2 ^ 2) = 16
应用：乘法
对于h = 2 ^ n - 1来说，其中n为整数，有：
h * a = (2 ^ n - 1) * a = (a * 2 ^ n) - a = (a << n) - a
有符号右移：>>
右移1位相当于除2，x >> n等价于x / (2 ^ n)。
int i = 4;
i = i >> 2; //4 / (2 ^ 2) = 1
无符号右移：>>>
应用：
求某m位数c的高n位：c >>> (m - n)
如：求32位int型变量c的高16位 —— c >>> 16
逻辑运算
按位与：&【有0则0】
1 & 0 = 0
1 & 1 = 1
0 & 0 = 0
应用:
- 判断奇偶
n & 1 == 1则为奇数，n & 1 == 0则为偶数
// 1 的二进制为：000…0001
int a = 5; // 奇数最后一位必为1，与1按位与，一定是000…0001
int b = 6; // 偶数最后一位必为0，与1按位与，一定是000…0000
//a & 1 = 1，奇数
//b & 1 = 0，偶数
- 判断是否是2的整数次幂
n & (n-1) == 0是2 ^ n，n & (n-1) == 1不是2 ^ n
//请看：
//4：100
//3：011
//8：1000
//7：0111
//可知：
//2 ^ n的二进制码必定是1000…000的格式，除了首位为1，其他都为0
//2 ^ n - 1的二进制码必定是0111…111的格式，除了首位为0，其他都为1
int isTrue = 16; //10000
int isFalse = 15; //01111
//isFalse - 1 = 14 ，二进制01110
//isTrue & (isTrue - 1) = 0，2 ^ n
//isFale & (isFalse - 1) = 01110，非2 ^ n
- 对2的整数次幂取模
m & (n - 1)等价于m % n。
注意：n必须要是 2 ^ n ！！！并不所有数都可以。
// HashMap中获取元素下标
// 将key.hashCode()前16位与后16位异或，求出一个hash值，这一步是为了让元素分布更加均衡
int hash = (key == null) ? 0 : ((key.hashCode()) ^ (key.hashCode() >>> 16));
// 将hash值对数组长度取模，将hash值映射成数组位置
int index = hash & (len - 1);
// 这也是为什么HashMap的容量一定要2 ^ n的原因 —— 方便位运算取模
- 求某m位数的低n位：c & ((1 << (m - n)) - 1)
如：求32位int型变量c的低16位 —— c & ((1 << 16 )- 1)
按位或：|【有1则1】
1 | 1 = 1
1 | 0 = 1
0 | 0 = 0
应用 :
- HashMap中的应用：最小的2的幂次方
//该方法可以保证返回一个能容纳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 = 65(1000001)为例，那么n = 64(1000000)
n >>> 1 = 0100000
n |= n >>> 1 = 1000000|0100000 = 1100000(96)
n |= n >>> 2 = 1100000|0011000 = 1111000(120)
n |= n >>> 4 = 1111000|0000111 = 1111111(127)
n |= n >>> 8 = 1111111|0000000 = 1111111(127)
n |= n >>> 16 = 1111111|0000000 = 1111111(127)
n + 1 = 128 = 2 ^ 7
按位非：~【取反】
0 则变为 1，1 则变为 0，如
~ 1 0 0 1 1 = 0 1 1 0 0
按位异或：^【相同则0，相异为1】
1 ^ 1 = 0
0 ^ 0 = 0
1 ^ 0 = 1
特点：
任何数和自己异或都是0：a ^ a = 0
0和任何数异或都是该数本身：0 ^ a = a
- HashMap中的应用：扰动函数
int hash = key.hashCode() ^ (key.hashCode() >>> 16);
//将高低16位进行异或，使得元素在HashMap上分布均匀
- 不用临时变量交换两个数
主要用到的原理就是a ^ (b ^ a) = b
//交换a和b的值
//a = a + b;
//b = a - b;
//a = a - b;
int a = -10;
int b = 11;
a = a ^ b;
b = a ^ b; //(a ^ b) ^ b = a
a = a ^ b; //(a ^ b) ^ (a ^ b) ^ b = b
//交换后a = 11, b = -10
//注意a和b不能是同一对象！！！！！！！
警惕以下情况——a和b出于某种原因，变成了同一个对象，那么以上代码都会出错：
//a = 2
a = a + a; //4
a = a - a; //0
a = a - a; //0
//a = 0
a = a ^ a; //0
a = a ^ a; //0
a = a ^ a; //0
//a = 0
