位运算

背景

为什么要做js位运算呢？

• 因为最近在学习hash算法，里面用到了大量的位运算

• 另外网上也找了很多资料，但大都比较片面，没有说明特殊情况时的处理，换几组数据计算结果就出错。

重温整数

ECMAScript 整数有两种类型，即：

• 有符号整数（允许用正数和负数）
• 无符号整数（只允许用正数） 在 ECMAScript 中，所有整数字面量默认都是有符号整数，这意味着什么呢？

有符号整数使用 31 位表示整数的数值，用第 32 位表示整数的符号，0 表示正数，1 表示负数。

数值范围从 -2147483647 到 2147483647。

位运算会把二进制数限制在32位，超出部分会被舍弃

调试位运算常用的几个方法

toString(2)

转换成2进制字符串

var a = 1732584193;
a.toString(2); // 1100111010001010010001100000001

parseInt(‘11001’, 2)

将2进制字符串转换成10进制数

parseInt('11001', 2) // 25

padStart(32, ‘0’)

字符串总长度，左边不足位数补0

'1100000001'.padStart(32, 0) // 00000000000000000000001100000001

源码、反码、补码

源码

将数字转换成的2进制数, 最左边表示符号位，1负数，0正数

5 源码： 0101
-10 源码：11010

反码

正数的反码与其原码相同

负数的反码，除符号位外，其他位取反

5 
源码：0101 
反码：0101

-10
源码：11010 
反码：10101

补码

正整数的补码与其原码相同

负整数的补码，取反码+1

5
源码：0101
补码：0101

-10
源码：11010
补码：10110

ok，现在开始正题

位运算符

• 非（~）
• 与（&）
• 或（|）
• 异或（^）
• 带符号左移（<<）
• 带符号右移（>>）
• 无符号右移（>>>）

位运算符：非（~）

运算步骤：

1. 将该数字取负数
2. 然后减1

~25 // -26

过程：

• 25取负：-25
• 减1：-26

~1  // -2
~-1 // 0
~100 // -101
~-100 // 99

位运算符：与（&）

运算步骤：

1. 把两个数转换成2进制补码
2. 相同位置进行比较（同为1，结果为1，否则为0）
3. 如果计算结果是负数，还要再做补码处理

如果位数不够，正数左边补0，负数补1

正正运算

10 & 3 // 2

过程：

• 10 补码：1010
• 3 补码： 0011
• 结果：0010，即 2

正负运算（1）

14 & -13 // 2

过程：

• 14 补码：01110（补一位符号位）
• -13 源码：11101，补码：10011
• 与运算：00010，即 2

正负运算（2）

88 & -19 // 72

过程：

• 88 补码：01011000（补一位符号位）
• -19 源码：110011，补码：101100
• 01011000 & 101100
• 负数（101100）位数不够，左边补1，即11101100
• 也就是 01011000 & 11101100
• 结果为：01001000，即：72

负负运算

-12 & -5 // -16

过程：

• -12 补码：10100
• -5 补码： 11011
• 与运算： 10000
• 结果为负，再取一次补码: 110000： -16

练习

3 & 7
-21 & 16
-271733879 & -1732584194
1125899778533470 & 812930
20 & 0xF
48192342 & 0xFFFF

位运算符：或（|）

运算步骤：

1. 把两个数字转换成2进制补码
2. 相同位置进行比较（有一个是1，结果即为1）
3. 如果计算结果是负数，还要再做补码处理

正正运算

10 | 3 // 11

过程：

• 10 源码：1010
• 3 源码：0011
• 结果：1011，即 11

正负运算

10 | -3 // -1

过程：

• 10补码：01010
• -3补码：11101
• 或运算：11111
• 结果为负，再取码：10001，即：-1

负负运算

-15 | -21 // -5

过程：

• -15 补码：110001
• -21 补码：101011
• 或运算：111011
• 结果为负再取补码：10101，即：-5

练习

15 | 20
40 | -14
-271733879 | 1732584193
(-271733879 & -1732584194) | (~-271733879 & 271733878)

位运算符：异或（^）

运算步骤：

1. 把两个数转换成2进制补码
2. 相同位置进行比较（必须是0和1或者1和0，结果才为1）
3. 如果结果为负，再取补码

正正异或

10 ^ 3 // 9

过程：

• 10 补码：1010
• 3 补码：0011
• 结果：1001，即 9

正负异或

10 ^ -3 // -9

过程：

• 10 补码: 01010
• -3 补码：11101
• 异或运算：10111
• 结果为负，再取补码：11001，即-9

负负异或

-10 ^ -3 // 11

过程：

• -10 补码：10110
• -3 补码：11101
• 异或运算：01011，即：11

练习

5 ^ 8
-10 ^ 9
-13 ^ -20
-271733879 ^ -1732584194 ^ 271733878

位运算符：带符号左移（<<）

运算步骤：

1. 把数字转换成2进制补码
2. 左移指定位数，右边补0
3. 如果结果未负数，再取补码

超过32位的部分舍弃

正数左移

1 << 2 // 补码：00000001 左移2位, 即 00000100，结果为：4
5 << 3 // 补码：00000101 左移3位, 即 00101000，结果为：40 

可以看出，正数带符号左移，即 a << n，其实是 a * 2的n次幂

负数左移

-3 << 4 

• -3 补码：101
• 左移4位 1010000
• 标志位为负，取补码：1110000，即-48

-6 << 3 // 1010 << 3 等于 1010000，取补码，1110000 即：-48
-11 << 4 // 10101 << 4 等于 101010000，取补码，110110000 即：-176

边缘情况

情况1：正数变负数

1732584193 << 2  // -1659597820

计算过程

• 1732584193转换成2进制源码：1100111010001010010001100000001（31位）
• 左移2位，补2个0：110011101000101001000110000000100（33位）
• 移除左边多余的1位：10011101000101001000110000000100（32位）
• 变为负数，取补码：11100010111010110111001111111100
• 即：-1659597820

情况2：负数变正数

-1732584193 << 2  // 1659597820

计算过程

• -1732584193转换成2进制：11100111010001010010001100000001（32位）
• 负数，取补码：10011000101110101101110011111111（32位）
• 左移2位：1001100010111010110111001111111100（34位）
• 多余部分舍弃：01100010111010110111001111111100（32位）
• 符号位为正，无需再补码，即：1659597820

练习

1 << 32 1 << 33 1 << 40 2147483648 << 2 1732584193 << 6 

位运算符：带符号右移（>>）

运算步骤：

1. 取数字二进制补码
2. 右移指定位数，左边补位与符号位一致
3. 多余位被舍弃
4. 如果计算结果为负，再取补码

正数右移

5 >> 1 // 0101 右移1位 0010，即 2
1 >> 2 // 0001 右移1位 0000，即 0

正数右移比较简单，移出的内容直接舍弃即可，左边用0补充

负数右移

-5 >> 2 // -2

分析：

• -5 补码：1011
• 右移2位：1110
• 结果为负，取补码：1010，即-2

练习

5 + 64 >> 9
1732584193 >> 4

位运算符：无符号右移（>>>）

运算步骤：

1. 把数字转换成32位2进制补码
2. 连同符号位，右移动指定的位数
3. 向右被移出的位被丢弃，左侧用0填充

因为符号位变成了 0，所以结果总是正的

正数右移

正数时候 >> 和 >>> 结果是一样的

5 >> 2 // 101 右移2位 001 即：1
5 >>> 2 // 101 右移2位 001 即：1

负数右移

-5 >>> 2 // 1073741822

过程：

• -5 源码: 10000000 00000000 00000000 00000101
• 补码：11111111 11111111 11111111 11111011
• 右移两位：00111111 11111111 11111111 11111110
• 转换成十进制即为：1073741822

问题：为什么这个要补满32位，而之前的运算都没有？

因为之前的运算，正数补的都是0，负数虽然补1，但计算后要做补码，补位的数最终不影响计算

而无符号右移，则会影响运算。所以需要补全

练习

-23 >>> 2
45678765 >>> 31

关于位运算的核心思路

• 运算前要取补码
• 运算结果导致负数，再取一次补码

以上内容都是个人收集、以及多次尝试整理的。

因为网上看到的很多文章计算方式都不对，虽然举的例子没问题，但几组数字就计算错误。

特此整理了该篇文章，与大家共同学习