位运算

2021-03-23

常见编码方式

1、移码

浮点数精度中IEEE-754中，我们知道了移码(双精度浮点数的阶码是右移了1023),是二进制数字编码方式的一种。

2、原码

原码非常简单直观，用第一位来表示数字的正负，剩余的位（bit）用来表示数值。看下 11 和 -11 在一个字节里用原码是如何表示的。

// +11
00001011
// -11 只有第一位不一样
10001011

原码表示的好处是符合直观理解，对阅读友好，缺点是对运算不友好，计算机无法直接拿这两个数做运算（比如加法）。

3、反码

反码是在原码的基础上，保留符号位，负数的数值位全部“取反”，如果原来是 1，变为 0，0 变为 1。

// +11
00001011
// -11 除了符号位，全部取反
11110100

这样编码之后，做运算就相当方便了，a + -a 会等于 11111111 (-0)。遗留的问题当然是，这样的编码产生了 0 和 -0。

同一个数字有两种表示势必会产生不必要的判断。于是补码出现了。

4、补码

补码是在反码的基础上继续优化，符号位任然不变，负数数值在原来的基础上 +1。

// +11
00001011
// 反码中的 -11
11110100
// 补码的 -11
11110101

由于加 1，a + -a 相加将会产生进位。

  00001011 (11)
+ 11110101 (-11)
________________
 100000000

多出来的一位会因为溢出被忽略掉，于是 a + -a = 0 仍然成立。这样设计之后 -0 就不存在了。00000000 取反之后再加一仍然是 00000000。
10000000 仍被用来表示负数，所以在补码的设计里面，负数比正式多了一位。在现代计算机系统中，提到位运算时都是使用补码。

js中和进制相关的方法

在位运算之前，先介绍一下两个常见的 Javascript 方法中和进制相关的方法 parseInt 和 Number.prototype.toString(base)

parseInt

parsetInt 相信所有人都非常熟悉了，常用它用将字符串转换成整数，第一个参数是需要解析的字符串，第二个参数是一个进制基数，表示需要按什么基数来理解这个字符串。

console.log(parseInt('1111', 2)) // 15
console.log(parseInt('1111', 8)) // 585
console.log(parseInt('1111', 16))// 4369
console.log(parseInt('1111'))// 1111

⚠️ 需要注意，大部分情况下，parseInt 会默认使用十进制来解析字符串，然而如果字符串以 0x 开头，会被认为是十六进制数。parseInt('0x21') === 33。而其他进制的字符串在 ES6 的标准中，比如 0o12(八进制)，0b11(二进制) 不会自动转换基数。所以为了保证最终运行结果的正确性和稳定性，parseInt 第二个参数不要省略。

Number.prototype.toString

Numer.prototype.toString干的事情恰好了 parseInt 相反，它支持传入一个基数，用于将数字转换成对应进制的表示。

1
2
3

console.log(15..toString(2));//1111
console.log(585..toString(8));//1111
console.log(4369..toString(16));//1111

例子中的 .. 是新学到的暗黑操作，数字字面量是不能直接调用原型链上的方法的，多一个点回被 JavaScript 解析成 Number 对象。也可以直接用 Number(15).toString(2) 的写法。
对了，需要当心，负数的 toString 方法会得到 - + 绝对值的对应进制表示。例如 -11..toString(2) 的结果是 -1011。如果需要得到正确的负数补码，可以使用后面会介绍的无符号右移。

位运算符

需要注意，在做位运算时所有的运算数以及运算结果只会保留 32 位的整数（为了方便后面的例子只使用8位），而在上一篇文章中我们知道，JavaScript 所能表示的最大安全数字范围是 -(2^53 - 1) ~ 2^53 - 1。不知道这个细节可能会对一些运算结果产生困惑。

1 2	Before: 11100110111110100000000000000110000000000001 After: 10100000000000000110000000000001

接下来将一一细数位运算及其应用，为了方便例子中使用 8 位的二进制表示。

按位与&

两个位都是 1 时，结果为 1，否则为 0

  00001011 (11)
& 00001001 (9)
__________
  00001001 (9)

常见应用
用于判断数字某一位是否为 1，例如可以使用 num & 1 来判断数字的奇偶性。

1 2	8(00001000) & 1 === 0 9(00001001) & 1 === 1

按位或|

两个位都是 0 时，结果为 0，否则为 1

  00001011 (11)
| 00001001 (9)
__________
  00001011 (11)

按位异或 ^

两个位都是 0 或者都是 1 时，结果为 0，否则为 1。任何数和自身异或结果都为零，和零异或结果都是其本身。

常见应用
按位异或经常出现在算法面试中，例如总共 n 个数 nums，有一个数出现了一次，其他数都出现了两次，O(n) 时间复杂度，O(0) 空间复杂度求这个只出现一次的数。
利用异或两两抵消的特性，把所有都异或起来就可以得到答案。

1	nums[0] ^ nums[1] ^ ... ^ nums[n - 1]

利用相互抵消特性的常见算法题还有不使用中间变量进行两个数字交换。

let a = 11
let b = 9
a = a ^ b // a ^ b
b = a ^ b // a ^ b ^ b = a
a = a ^ b // a ^ b ^ a ^ b ^ b = b

按位非 ~

按位非是 1 变为 0，0 变为 1，结果按补码形式出现。

1
2
3

~ 00001001 (9)
_______________
  11110110 (-10)

左移 <<

把数值的二进制表示向左移位，移除的位会被遗弃，末尾补 0

1
2
3

01100001 << 2
____________________
10000100

常见应用
左移一位相当于将数值在原来的基础上乘以2。需要留意位运算只有 32 位的问题。超过 32 位会产生”诡异“的结果。

1 << 30 // 1073741824
1 << 31 // -2147483648
1 << 32 // 1
3 << 31 // -2147483648
3 << 32 // 3

右移 >>

把数值的二进制表示向右移位，末尾的位会被遗弃，前面的位会按符号位来补，符号位是 1，补 1，符号位是 0，补 0。

1
2
3

11010011 >> 1
____________________
11101001

常见应用
右移一位相当于将数值在原来的基础上除二取整。

无符号右移 >>>

无符号右移，顾名思义就是右移的时候，不考虑符号位，前面统统补 0。

1
2
3

11010011 >>> 1
____________________
01101001

常见应用
在 JavaScript 中，不存在无符号整数的类型，并且二进制运算只能保留 32 位结果（而 JS 的最大安全表示范围可以到 53 位）。如果需要在位运算过程中保留32位无符号的结果，可以使用无符号右移运算符，它的结果就是 32-bit 无符号整数。

1 2	1 << 31 // -2147483648 1 << 31 >>> 0 // 2147483648

前面提到负数执行 Number.prototype.toString(2) 的结果得不到补码，使用无符号右移就可以了。

1 2	(-11 >>> 0).toString(2) "11111111111111111111111111110101" （4294967285）