JavaScript中的位运算

按位操作符

JavaScript 中使用 IEEE-754 64 位存储。位操作符不能直接操作 64 位的值，而是将它转换为二进制补码形式的 32 位的整数，最后再将结果转为 64 位。32 位中 31 位表示整数的值，第 32 位为符号位（0 为正数，1 为负数）。每一位由二进制数存储，31 位中的每一位的索引表示 2 的次幂乘与每一位的 0 或者 1。没有使用到的位将使用 0 填充。

举一个例子????。31 的 32 位二进制数表示为 0000 0000 0000 0000 0000 0000 0001 1111。第 32 位 0 表示符号位，11111 为有效位。

1	1	1	1	1
2^4 * 1	2^3 * 1	2^2 * 1	2^1 * 1	2^0 * 1
16	8	4	2	1

负数

负数使用二进制存储，但是使用 二进制补码 表示

如何求一个数的二进制补码？

• 1. 求出该数绝对值的二进制码
• 1. 将获得的二进制码取反（1 变成 0，0 变成 1）
• 1. 二进制码加 1

举一个例子????。如何求出 -31 的二进制补码。-31 的二进制补码的结果为 1111 1111 1111 1111 1111 1111 1110 0001。

• -31 的绝对值为 31，求出 31 的二进制的码

0000 0000 0000 0000 0000 0000 0001 1111

• 将 31 的二进制码的 0 和 1 颠倒

1111 1111 1111 1111 1111 1111 1110 0000

• 将二进制码加 1

1111 1111 1111 1111 1111 1111 1110 0000
                                     +1
---------------------------------------
1111 1111 1111 1111 1111 1111 1110 0001

无符号数

ECMAScript 所有整数都是有符号位的。在无符号数中，第 32 位不表示符号，因为无符号数只能是正数，32 位无符号数可以表示更大的数。

特殊值的处理

在 NaN 和 Infinity 在位运算符中会被当作 0 处理。非数值类型会先使用 Number() 处理，然后再应用位操作符。

按位非(NOT)

按位非 ~ 会将数值的 32 位二进制的每一位取反 (0 变为 1，1 变为 0)。按位非的操作符的本质 取操作数的负值，然后减一。

// -24
~23

// -101
~100

// 9
～-10

// 100
～-101

举一个例子????。10 进行按位非之后的结果，等于 -11

0000 0000 0000 0000 0000 0000 0000 1010
// ~ NOT
1111 1111 1111 1111 1111 1111 1111 0101

按位与(AND)

按位与 &, 本质上将两个操作数的 32 位二进制数的每一位对齐。然后按如下的规则取值，1 & 1 等于 1；1 & 0 等于 0；0 & 1 等于 0；0 & 0 等于 0。

举一个例子????。10 和 5 之间进行按位与操作的结果，等于 0

0000 0000 0000 0000 0000 0000 0000 1010
// & AND
0000 0000 0000 0000 0000 0000 0000 0101
// 等于
0000 0000 0000 0000 0000 0000 0000 0000

按位或(OR)

按位与 |, 本质上将两个操作数的 32 位二进制数的每一位对齐。然后按如下的规则取值，1 | 1 等于 1；1 | 0 等于 1；0 | 1 等于 1；0 | 0 等于 0。

举一个例子????。10 和 5 之间进行按位或操作的结果，等于 15

0000 0000 0000 0000 0000 0000 0000 1010
// & OR
0000 0000 0000 0000 0000 0000 0000 0101
// 等于
0000 0000 0000 0000 0000 0000 0000 1111

按位异或(XOR)

按位异或 ^, 本质上将两个操作数的 32 位二进制数的每一位对齐。然后按如下的规则取值，1 ^ 1 等于 0；1 ^ 0 等于 1；0 ^ 1 等于 1；0 ^ 0 等于 0。

举一个例子????。10 和 5 之间进行按位异或操作的结果 15。

0000 0000 0000 0000 0000 0000 0000 1010
// ^ XOR
0000 0000 0000 0000 0000 0000 0000 0101
// 等于
0000 0000 0000 0000 0000 0000 0000 1111

左移

左移 (<<) 将 32 位二进制向左移动指定的位数，空缺的位将会使用 0 填充。左移不会影响符号位

举一个例子????。将 5 左移 2 位，等于 20

0|000 0000 0000 0000 0000 0000 0000 0101
// <<2
0|000 0000 0000 0000 0000 0000 0001 0100
// 等于
(2^0 * 0) + (2^1 * 0) + (2^2 * 1) + (2^3 * 0) + (2^4 * 1) = 0 + 0 + 4 + 0 + 16 = 20

有符号位右移

右移 (>>) 将 32 位二进制向右移动指定的位数，但是保留符号位，右移空缺的符号位使用 0 填充

举一个例子????。将 31 有符号右移 3 位，等于 3。

0|000 0000 0000 0000 0000 0000 0001 1111
// >>3
0|000 0000 0000 0000 0000 0000 0000 0011
// 等于
(2^0 * 1) + (2^1 * 1) = 1 + 2 = 3

无符号位右移

无符号位右移，会将所有 32 位数都向右移动。对于正数来说右移和无符号位右移的结果是一致的。

举一个例子????。将 -31 无符号右移 28 位。

1111 1111 1111 1111 1111 1111 1110 0001
// >>> 28
0000 0000 0000 0000 0000 0000 0000 1111
// 等于
(2^0 * 1) + (2^1 * 1) + (2^2 * 1) + (2^3 * 1) = 1 + 2 + 4 + 8 = 15

位操作符的奇妙用法

~~ 向下取整

按位非~。将操作数取负值，并减 1。对于浮点数，会直接舍弃小数的部分。比如~11.1 === -12。然后将结果，再次执行按位非操作，就会得到了去除小数位的原数字，~-12 === 11。因此我们可以使用~~ 代替 Math.floor。

// 12
~~12.5

// 6
~~6.1

// 8
~~-8.1

Math.floor 和~~ 性能对比

我分别使用 和 Math.floor，对包含了 10000000 个浮点数的数组，进行向下取整。耗时 386 毫秒，Math.floor 耗时 411 毫秒.

~ 判断索引是否存在

• ~- 1 等于 0（- 1 取正值后减 1）

平时使用 indexOf 等 API 时，当查询的字符串不存在时，indexOf 会返回 -1。但是 Boolean(-1) 等于 true，所以我们在使用时通常需要添加一个判断 '字符串'.indexOf('字') > -1，看上去并不是那么的简洁。
- 1 按位非等于 0，而 Boolean(0) 是等于 false 的。所以我们可以把不等式简化成下面的样子。

if ('米莉波比布朗'.indexOf('莉') > -1) {
}

// 等价于
if (~'米莉波比布朗'.indexOf('莉')) {}

^ 不使用额外的空间交换两个变量的值

在了解这个技巧之前需要先了解两个准则：

1. 两个相同的数进行按位异或等于 0
2. 任意一个数与 0 进行按位异或等于自身

// 0
100 ^ 100
// 0
-99 ^ -99

// 100
100 ^ 0
// -2
0 ^ -2

在代码中交换两个变量的值，通常是通过第三个变量，或者使用 ES6 中的解构赋值

// 使用第三个变量
var a = 1
var b = 2
var c = a
a = b
b = c

// 使用解构赋值
var x = 1
var y = 2
[x, y] = [y, x]

使用异或按位运算符

let a = 2
let b = 3

a = a ^ b
// b = a ^ b ^ b => a ^ (b ^ b) => a ^ 0 = a
b = a ^ b
// a = a ^ b ^ a ^ b ^ b => (a ^ a) ^ (b ^ b) ^ b => 0 ^ 0 ^ b => 0 ^ b = b
a = a ^ b

^ 切换位

使用异或按位运算符，可以用来切换二进制数中的某些位，这基于这样一个事实：

1. 任意一个数与 0 进行按位异或等于自身（上面提到过）
2. 任意一个数与与 1 进行按位异或，总是被切换（参考下面的例子）

let a = 1
// 0
a = 1 ^ 1
// 1 (又变回了 1)
a = a ^ 1

举一个例子????，let a = 0b101011, 我们想将中间的四位进行切换 (0->1, 1->0) 变为0b110101。我们创建一个掩码，首尾为 0，中间四位为 1, 使用掩码进行按位异或的操作。

// 掩码
let mask = 0b011110
let a = 0b101011

// 0b110101
a ^ mask

& 关闭高位

使用按位与 &, 可以用来关闭二进制数中的某些位，这基于这样一个事实：

1. N & 0 === 0 任意一个数与 0，按位与，等于 0
2. N & N === N 任意一个数与自身，按位与，等于自身
3. N & -N === 0 任意一个数与自身负值，按位与，等于 0
4. N & -1 === N 任意一个数与 -1，按位与，等于自身

比如我们有一个 8 位的二进制数，我们需要关闭后 4 位(设置为 0)，我们首先创建一个 8 位的位掩码，位掩码的后四位设置为 0，前四位设置为 1。接下来使用位掩码与操作数进行按位与操作

const mask = 0b00001111

// 结果 00001010，成功将后四位设置为 0
mask & 0b10101010

& 检查设置位

可以使用按位与，检查二进制数中某一位是否设置了。

举一个例子????，我们需要检查第五位是否有数字。

const mask = 0b10000

// false
0b100010 & mask === mask

// true
0b110010 & mask) === mask)

& 判断奇数或偶数

奇数与偶数的二进制表示的特性：

• 偶数的二进制的第一位始终是 0
• 奇数的二进制的第一位始终是 1

// 0b0
0
// 0b1
1
// 0b10
2
// 0b11
3
// 0b100
4
// 0b101
5
// 0b110
6

所以我们可以使用 0001 作为掩码，使用 0 关闭高位，只保留第一位。当number & 1 === 1, number 为奇数。number & 1 === 0, number 为偶数。

• 偶数与 0b1，按位与，结果必定等于 0
• 奇数与 0b1，按位与，结果必定等于 1

// 奇数
(3 & 1) === 1

// 偶数
(4 & 1) === 0

<<，>> 移位实现乘除法

ps：???? 在工程中，最好不要这样写，免得的被打。

左移 1 位，等于乘以 2，左移 2 位，等于乘以 4。但是对于乘以 7 或者乘以 9 该怎么办呢？乘以 7，可以分解为左移 3 位并减去一位，a * 7 === (a << 3) - a。乘以 9，可以分解为左移 3 位并加上一位a * 9 === (a << 3) + a

• 左移 1 位，等价于，乘以 2 的 1 次方。
• 左移 2 位，等价于，乘以 2 的 2 次方。
• 左移 3 位，等价于，乘以 2 的 3 次方。
• …

a * 2 === a << 1
a * 3 === (a << 1) + a
a * 4 === a << 2

• 右移 1 位，等价于，除以 2 的 1 次方。
• 右移 2 位，等价于，除以 2 的 2 次方。
• 右移 3 位，等价于，除以 2 的 3 次方。
• …

a / 2 === a >> 1
a / 4 === a >> 2
a / 8 === a >> 3

利用位操作符，解答 leetcode

• 利用右移，「leetcode」29. 两数相除
• 利用异或，「leetcode」136. 只出现一次的数字
• 利用异或，「leetcode」268. 缺失数字
• 利用按位与，「leetcode」191. 位 1 的个数
• 利用右移和按位与,「leetcode」78. 子集
• 利用按为与,「leetcode」231.2 的幂
• 利用异或和按位与，「leetcode」371. 两整数之和

从这些题目中，可以 get 到的点

1. 2 的 n 次幂，二进制中只有一个 1。2 的 n 次幂与 2 的 n 次幂减一，按位与，结果永远是 0。
2. 可以使用 >>> 右移代替除法
3. 可以使用二进制的 0 和 1，模拟有或无
4. 异或可以用来实现简单的去重
5. 异或配合按位与可以实现加法

参考

• 按位操作符
• Interesting use cases for JavaScript bitwise operators
• 巧用 JS 位运算
• JavaScript 高级程序设计