一篇讲清楚移位和异或

位运算看起来很“底层”，但在很多高性能代码里都很常见。比如 HashMap 的哈希扰动、权限标记、状态压缩、加密算法、布隆过滤器，背后都离不开移位和异或。

这篇文章专门讲两个最常见、也最容易混淆的位运算：

• 移位：<<、>>、>>>
• 异或：^

目标不是死记语法，而是理解它们到底在“按位”做什么。

一、先理解什么叫“按位运算”

计算机里整数最终都是二进制。

例如十进制的 13，二进制可以写成：

00001101

如果对这个数做普通加减乘除，是把它当作一个整体来算；如果做位运算，就是直接对每一个二进制位操作。

所以位运算的关键不是“数学意义”，而是“二进制位如何变化”。

二、移位运算

Java 里常见的移位有三种：

<<   左移
>>   右移（带符号）
>>>  无符号右移

1. 左移 <<

左移的规则是：所有二进制位整体向左移动若干位，右边补 0。

例如：

3 << 2

先看 3 的二进制：

00000011

左移两位：

00001100

结果是十进制 12。

所以：

3 << 2 = 12

从数学效果上看，左移一位大致相当于乘以 2，左移两位大致相当于乘以 4。

例如：

5 << 1 = 10
5 << 2 = 20

但“相当于乘法”只是便于理解，真正发生的是二进制位左移，不是做乘法指令。

2. 右移 >>

右移的规则是：所有二进制位整体向右移动若干位，左边补什么，取决于符号位。

>> 是带符号右移，也叫算术右移：

• 如果原数是正数，左边补 0
• 如果原数是负数，左边补 1

例如：

8 >> 2

8 的二进制：

00001000

右移两位：

00000010

结果是 2。

所以：

8 >> 2 = 2

从效果上看，右移一位大致相当于除以 2。

3. 无符号右移 >>>

>>> 和 >> 的区别在于左侧永远补 0，不管原来是正数还是负数。

这对正数来说通常和 >> 一样，但对负数差别很大。

例如在 int 中，-1 的二进制是 32 个 1：

11111111 11111111 11111111 11111111

如果执行：

-1 >> 1

因为是带符号右移，左边补 1，结果仍然接近负数表示：

11111111 11111111 11111111 11111111

结果还是 -1。

但如果执行：

-1 >>> 1

左边补 0，结果就变成：

01111111 11111111 11111111 11111111

这是一个很大的正数。

所以：

• >> 保留符号
• >>> 不保留符号，只做逻辑右移

4. 移位的常见用途

快速乘除 2 的幂

x << 3   // 近似 x * 8
x >> 2   // 近似 x / 4

构造二进制掩码

1 << 3   // 00001000
1 << 5   // 00100000

这类写法常用于权限位、状态位、标志位。

哈希扰动和位混合

h ^ (h >>> 16)

这里就用到了无符号右移，把高位信息移动到低位附近，再与原值异或。

三、异或运算 ^

异或是位运算里最值得单独掌握的一个。

规则只有一句话：

相同为 0，不同为 1

看真值表更清楚：

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

1. 一个简单例子

例如：

10 ^ 6

先转成二进制：

10 = 1010
 6 = 0110

逐位异或：

1010
0110
----
1100

结果是十进制 12。

所以：

10 ^ 6 = 12

2. 异或的几个重要性质

这些性质非常实用，比单纯记规则更重要。

性质一：任何数和 0 异或都等于它自己

a ^ 0 = a

因为每一位和 0 比较时，都保持原值不变。

性质二：任何数和自己异或都等于 0

a ^ a = 0

因为每一位都相同，相同异或结果为 0。

性质三：异或满足交换律和结合律

a ^ b = b ^ a
(a ^ b) ^ c = a ^ (b ^ c)

这意味着多个数异或时，可以调整顺序。

性质四：可以“可逆”

如果：

c = a ^ b

那么：

c ^ b = a
c ^ a = b

因为：

(a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a

这也是为什么异或常被用于“加密/解密”“还原原值”“交换变量”等场景。

四、异或的常见应用

1. 找出只出现一次的数字

这是异或最经典的应用之一。

例如数组：

[2, 3, 2, 4, 4]

除了 3，其他数都出现两次。

把所有元素异或起来：

2 ^ 3 ^ 2 ^ 4 ^ 4

根据交换律和结合律，可以重排：

(2 ^ 2) ^ (4 ^ 4) ^ 3

因为：

2 ^ 2 = 0
4 ^ 4 = 0
0 ^ 0 ^ 3 = 3

所以最后结果就是只出现一次的那个数。

2. 不借助临时变量交换两个数

经典写法：

a = a ^ b;
b = a ^ b;
a = a ^ b;

虽然现在工程里一般不推荐这样写，因为可读性差，但它能说明异或的可逆性。

3. 简单加密和掩码处理

如果一个值用同一个“密钥”做两次异或，会还原原值：

data ^ key ^ key = data

这在某些简单编码、状态翻转、校验处理中很常见。

4. 判断两个值是否不同

异或结果不为 0，表示至少有一位不同：

(a ^ b) != 0

这说明 a 和 b 不相等。

五、移位和异或为什么经常一起出现

很多底层代码会把两者组合使用，因为它们各自解决不同问题：

• 移位：把某些位移动到目标位置
• 异或：把不同来源的位信息混合起来

例如：

h ^ (h >>> 16)

这里可以分两步理解：

1. h >>> 16
   把高 16 位移动到低 16 位区域
2. h ^ (h >>> 16)
   让原始值和移动后的值按位比较并混合

结果就是：

• 原始高位信息被带到了低位
• 低位的区分度增强
• 后续如果只依赖低位，也能获得更好的散列效果

这就是 HashMap、哈希算法、位混合函数里频繁出现“移位 + 异或”组合的原因。

六、几个容易混淆的点

1. >> 和 >>> 不是一回事

很多初学者只记得“都是右移”，但它们对负数影响完全不同。

• >>：保留符号位
• >>>：左边统一补 0

如果在哈希、位混合、二进制协议解析里写错，结果会完全不同。

2. 左移不等于永远安全地乘 2

左移虽然常常相当于乘 2 的幂，但如果高位被移出范围，会发生溢出。

所以它不是“数学上精确无风险的乘法替代”，而是“固定宽度整数上的位移动作”。

3. 异或不是加法

有些人会把异或理解成“无进位加法”，这个说法在某些场景下有帮助，但不能完全等同。

最稳妥的理解方式还是：

异或只看每一位是否相同，相同为 0，不同为 1。

七、总结

移位和异或本质上都是直接操作二进制位：

• <<：向左移动，右边补 0
• >>：带符号右移，左边补符号位
• >>>：无符号右移，左边补 0
• ^：按位异或，相同为 0，不同为 1

如果只记一个结论，可以记下面这句：

移位负责“搬运位”，异或负责“比较并混合位”。

理解了这句话，再去看 HashMap、位图、权限标记、哈希扰动、状态压缩等代码时，很多看起来“神秘”的位运算就会变得非常直接。