JS探幽——移位运算符 <<，>> 和 >>>
#ECMAScript#JS探幽#移位运算符 2022-09-09

移位运算符在数据结构与算法中有着重要的作用，很多时候可以大大提高算法性能，简化问题求解。同时也是高级语言连接计算机机器码的工具。本文介绍了 JavaScript 中移位运算符 <<，>> 和 >>> 的规范和表现。

前言

可能很多前端开发者对位运算并不感冒，觉得过于接近于 C、C++ 等语言的风格以至于与 JavaScript 简单易用的风格所不符。事实确实如此，大多数情况下位运算都可以用普通的数值操作符替代实现，并且前端开发者对于接近于底层的性能优化并不敏感。诸多有关位运算的优化算法又过于晦涩1，深入了解又不免过于消耗精力。但有时稍花费一点时间了解一些常用的位操作技巧，能够提升编码的效率和性能。例如，在 JavaScript 中求两数中间的整数，即可使用移位操作简化代码：

1
2
3
4
let a = 0, b = 11, mid

mid = Math.floor((a + b) / 2)  // 使用四则运算并调用函数
mid = (a + b) >> 1  // 求和后直接向右移位

既然要用，那么就要对其规范和表现有一个准确的了解，使用时遇到意外的表现也可快速定位问题。

引例

照例，在阅读本文前请思考下面的代码，考虑它们的预期处理结果是什么。如果你能完全预料和理解这种表现，那么无需拨冗阅读本文了。如果一些表现使你疑惑，也许能从本文得到答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*-- part 1 --*/
1 << 31 === 2 << 30 // true
1 << 32 === 2 << 31 // false

1 << 30 === Math.pow(2, 30)  // true
1 << 31 === Math.pow(2, 31)  // false

2 << 29 === Math.pow(2, 30)  // true
2 << 30 === Math.pow(2, 31)  // false


/*-- part 2 --*/
1 >> 31 === 0 // true
1 >> 32 === 1 // true
1 >> 33 === 0 // true
2 >> 31 === 0 // true
2 >> 32 === 2 // true

/*-- part 4 --*/
-1 >> 1 === -1 // true
-1 >> 2 === -1 // true
-1 >> 32 === -1 // true

-2 >> 1 === -1 // true
-2 >> 31 === -1 // true
-2 >> 32 === -2 // true
-2 >> 33 === -1 // true

/*-- part 5 --*/

-1 >>> 1 === 2147483647 // true

JS 的移位运算符

其实引例中的表现均可用以下几个规则来解释：

  1. 位运算符将被操作数视作由 0 和 1 构成 32 位的二进制数串2
  2. 按照第一条规则转换数字时使用 32 位二进制补码表示
  3. 移位操作的移动位数为右操作数对 32 取模后的值，例如 a << 33 === a << 1，a << -31 === a << 1

根据以上规则，再结合 << >> 和 >>> 3 种运算符的具体规则2：

  • << 左移位运算符，将左操作数的 32 位补码每个数位的数都向左移动指定位数，左溢出的数字舍弃，右侧补 0
  • >> 有符号右移位运算符，将左操作数的 32 位补码每个数位的数都向右移动指定位数，右溢出的数字舍弃，左侧根据原操作数的最高位补 0 或 1
  • >>> 无符号右移位运算符，将左操作数的 32 位补码每个数位的数都向右移动指定位数，右溢出的数字舍弃，左侧补 0

有了以上规则，JavaScript 的移位操作符的运算结果就都能正确判断了。至此文章的核心内便已经结束，如果你已经熟悉其它语言的移位运算，那么只需要参考以上规则即可。下面结合具体例子进行解释。

计算机的补码

在开始介绍具体的运算符前，先简单回顾下计算机的补码。计算机的补码是为了简化整数间的减法运算而设计的一种非常巧妙地编码方式，这里只简单的介绍补码的编码规则，以备后用。

对于 32 位整数来说，正数的补码与原码一致，由于最高位为符号位固定为 0 表示正数，故 32 个数位所能表示的正整数范围为 。数字 0 的补码则表示为 32 个 0。对于负数来说，首先最高位固定为 1 表示负数，剩余数位则在其原码的基础上“取反加1”。例如 -1 的原码为 10000000000000000000000000000001，则先对其非符号位取反得到 11111111111111111111111111111110，然后再加 1，得到 -1 的补码为 11111111111111111111111111111111。容易验证“-0”的原码在补码下表示 ，故负整数的取值范围为 。

<< 运算符

根据规定，左移位运算符无非就是将所有数位左移，并在右侧补零。对于正整数来说，左移几位就是在原来的数乘上 2 的几次（对 32 取模后）幂：

1
num << n === num * Math.pow(2, n mod 32)

当然，上述公式基于所有数值对于 32 位整数来说没有溢出。当溢出时，将按照 32 位补码溢出处理。例如引例中 2 << 31，即将二进制 10 所有数位向左移动 31 位，显然第 2 位的 1 最终会移至（从右到左数）第 “33” 位，导致溢出被舍弃，最终所有数位皆为 0，因此 2 << 31 === 0。而对于 1 << 32，由于右操作数对 32 取模后为 0，故并不移位 1 << 32 === 1。

同理，当左操作数对于 32 位整数溢出时，仍然先处理溢出后在进行移位操作。此处，仅举例：(Math.pow(2,32) + 1) << 1 === 2。

另外需注意，左移操作时虽然限制了右操作数对 32 取模，但仍无法避免左侧溢出数位被舍弃。这就可能导致当操作数较大时，正数左移位后变为负数。例如，2 << 30 === -2147483648 // -2^31。

>> 运算符

右移位运算符和 << 左移位运算符对于溢出和取模的处理一致，不再赘述。但 >> 在补位的处理上略有不同，<< 运算符在右侧直接补 0。而 >> 运算符视被操作数的最高位选择补 0 或 1。具体地，当被操作数最高位为 0（即为正数或零）则补 0，反之补 1。也就说右移运算符保证了操作前后的符号。并且也解释了为什么对于 -1 >> n 无论 n 为多少结果都为 -1。因为 -1 的补码在各个数位上为 1，则右侧被移除多少个 1，左侧就会被补进来多少个 1，故并不改变数值大小。

>>> 运算符

介绍完前两个运算符，无符号的右移运算符就一目了然了。该运算符与 << 除了在移动方向上不同外，其余溢出、补零等规则都一致，不再赘述。仅解释引例中 -1 >>> 1 === 2147483647。由于 -1 的补码为 111...111，故右移一位后，右侧被舍弃一个 1，左侧最高位补 0，则变为 0111...111，显然该值为 。与 << 运算符一致，>>> 也可能使操作数发生符号变化。

有关对于 32 取模的规则未找到官方文档支持，仅实验推断，并且未发现反例，读者可自测。

参考资料

[1] HENRY S. WARREN J. 算法心得：高效算法的奥秘（原书第2版）[M/OL]. 爱飞翔, 译. 机械工业出版社, 2014[2022-09-09]. https://book.douban.com/subject/25837031/.

[2] Expressions and operators - JavaScript | MDN[EB/OL]. [2022-09-09]. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Expressions_and_Operators#bitwise_operators.