2023-07-28 15:02

关注

JavaScript 位运算

开篇

位运算 在 JS 中是一种对 Number 数字 进行数值运算的方式，它会将操作数转为 Int32（32 位有符号二进制值，每一位值叫做 比特位，由 0 和 1 组成）进行位运算，执行完后会将 Int32 转为对应的浮点数（十进制值）。

操作数的大小超过 Int32 范围(-2^31 ~ 2^31-1). 超过范围的二进制位会被截断, 取低位 32bit。

在 JS 中 Number 数字表示形式有（进制）：

1. 十进制（满10进1，我们日常生活使用的都是十进制数字表示）
123456789
20

2. 二进制，以 0b、0B 作为前缀（计算机中常使用二进制来表示）
0b111010110111100110100010101 --> 123456789
0b10100 --> 20

> 十进制转二进制：num.toString(2)；
> 二进制转十进制：parseInt(二进制值, 2).

3. 八进制，以 0o、0O 作为前缀
0o726746425 --> 123456789
0o24 --> 20

> 十进制转八进制：num.toString(8)；
> 八进制转十进制：parseInt(八进制值, 8).

4. 十六进制，以 0x、0X 作为前缀
0x75bcd15 --> 123456789
0x14 --> 20

> 十进制转十六进制：num.toString(16)；
> 十六进制转十进制：parseInt(十六进制值, 16).

一、位运算操作符

JavaScript 中的常用的按位操作符如下，

1. 按位与（AND）

用法：a & b
描述：对于每一个 bit 位，只有两个操作数相应的 bit 位都是 1 时，结果才为 1，否则为 0。
代码示例：

// 计算 3 & 2，首先将操作数转化为 Int32：

// 3对应的 Int32
0b000 0000 0000 0000 0000 0000 0000 0011 
// 2对应的 Int32
0b000 0000 0000 0000 0000 0000 0000 0010 

// 为了直观理解，我们排除前面的 0，只保留最后8位（实际参与计算的是全部的 32 位）：
  0000 0011
& 0000 0010
-----------
  0000 0010

// 最终，3 & 2计 算结果转化为浮点数后为 2。

console.log(0b0011 & 0b0010); // 得到 2，0b0010 -->（2^0 + 2^1 = 2）

2. 按位或（OR）

用法：a | b
描述：对于每一个 bit 位，当两个操作数相应的 bit 位至少有一个 1 时，结果为 1，否则为 0。
代码示例：

console.log(0b0010 | 0b0010); // 得到 0b0010 --> 2
console.log(0b0110 | 0b0010); // 得到 0b0110 6（2^0 + 2^1 + 2^2 = 6）

3. 按位异或（XOR）

用法：a ^ b
描述：对于每一个 bit 位，当两个操作数相应的 bit 位有且只有一个 1 时，结果为 1，否则为 0。
代码示例：

console.log(0b0010 ^ 0b0010); // 得到 0b0010 --> 0
console.log(0b0110 ^ 0b0010); // 得到 0b0100 --> 4（2^0 + 2^0 + 2^2 = 4）

4. 按位非（NOT）

用法：~a
描述：将操作数的二进制表示的每个位取反，即 0 变为 1，1 变为 0，然后返回「整数」结果。
代码示例：

console.log(~0b0010); // ~2 得到 -3

对于一个正数，~正数经过按位非操作后得到的结果是： -(x + 1)。这是因为 ~ 会将 32 位二进制的符号位（第一位，即最高位）0 变为 1 变成负数，负数需要进行「补码 + 1」所以～2 最终得到 -3。

这里提到的负数转换规则，可以查看下文「扩展知识」中的「负数的二进制表示」。按位非通常结合按位与一起使用，如下文的删除权限。

5. 左移（Left shift）

用法：a << b
描述：将 a 的二进制形式向左移 b (< 32) 比特位，并且使用 1 填充，相应的右边会增加 b（<32）比特为，用 0 填充。
代码示例：

let A = 0b1111; // 15
console.log(A << 1); // 30（0b1111 --> 0b11110）
console.log(A << 2); // 60（0b1111 --> 0b111100）

6. 有符号右移

用法：a >> b
描述：将 a 的二进制表示向右移 b (< 32) 位，丢弃被移出的位。
代码示例：

let A = 0b1111; // 15
console.log(A >> 1); // 7（0b1111 --> 0b111）
console.log(A >> 2); // 3（0b1111 --> 0b11）

7. 无符号右移

用法：a >>> b
描述：将 a 的二进制表示向右移 b (< 32) 位，丢弃被移出的位，并使用 0 在左侧填充。
代码示例：

let A = 0b1111; // 15
console.log(A >>> 1); // 7（0b1111 --> 0b0111）
console.log(A >>> 2); // 3（0b1111 --> 0b0011）

有符号右移与无符号右移主要区别在于用于填充左侧空缺位的值不同。在对负数的处理上表现明显：

let A = 1;
let B = -1;
console.log(A >> 0, B >> 0); // 1 -1
console.log(A >>> 0, B >>> 0); // 1 4294967295

无符号右移在 JS 中常被用作处理数组索引下标为 -1 的时候，省去了判断 -1 的逻辑。如 events 发布订阅：

// event.off
this._eventMap[type].splice(this._eventMap[type].indexOf(handler) >>> 0, 1);

二、扩展知识 - 负数的二进制表示

在计算机内存中二进制数中有两种表示方式：原码和补码。常见的正数采用原码形式，如正数 1 的二进制表示为 0001；负数在计算机内存中则采用补码表示。

如现在有一个负数 -1，

在计算机中，二进制数的长度为 32 位，其中左侧第一位（最高位）是一个符号位也是 0 和 1 组成，其中 0 代表是正数，1 代表是负数。

对于正数 1 在内存中采用原码表示为：0000...0001；对于负数 -1，在内存中需要经过原码 --> 反码 --> 补码，最终使用补码来表示。

1）-1 的原码表示为：1000...0001，第一位（符号位）是 1；

2）接着转换为反码，符号位 1 不动，其余位取反（0 变 1，1 变 0）变成：1111...1110；

3）反码加上 1 后得到的就是 -1 的补码，最终得到 32 位的 1111...1111。

根据这个规则就能推算出 -2、-3、-4 在计算机内存中的二进制表示值：

-2，
原码： 1000...0010
反码 + 1： 1111...1101 + 1 --> 1111...1110

-3，
原码： 1000...0011
反码 + 1： 1111...1100 + 1 --> 1111...1101

-4，
原码： 1000...0100
反码 + 1： 1111...1011 + 1 --> 1111...1100

试想一下，操作符按位非 ~ 对 -1 做处理会怎样呢？按位非会将 -1 的 32 位二进制 1111...1111 变为 0000...0000，最终得到一个 0。利用这一特点，可以用于简化对数组匹配得到 -1 的处理方式。

如：判断 url 上是否存在 ?

url += ~url.indexOf("?") ? "&" : "?";

三、位运算在权限系统中的应用

在权限系统中，一个角色可能具备一个或多个权限，位运算可以很好地处理这种关系。

位运算运用在权限系统中，需要遵循两个规则：

每一种权限码保持唯一；
权限码均以二进制数形式，有且只有一位值为 1，其余全部为 0（即权限值为：2^n）

位运算在权限系统中使用的运算操作：

| 按位或，用来赋予权限（添加权限，使得角色存在多种类型权限）
& 按位与，用来校验权限（校验权限，判断角色是否具备某个权限）
^ 按位异或，用来校验权限（删除权限，移除角色上的某个权限）

比如 linux 的文件权限分为读、写和执行，分别使用不同二进制值表示：4、2、1（2^n 表示）

权限字母表示数字表示二进制

读	r	4	0b100
写	w	2	0b010
执行	x	1	0b001

下面我们借助位运算操作符，模拟实现 linux 文件权限的添加、校验和删除。

1. 添加权限

let r = 0b100
let w = 0b010
let x = 0b001

let user = r | w | x; // 使用 | 操作符 赋予权限

console.log(user); // 7
console.log(user.toString(2)); // 0b111

r | w | x 会让 user 的三个二进制位都为 1，表示同时拥有三个权限。

2. 校验权限

let r = 0b100
let w = 0b010
let x = 0b001

let user = r | w; // 赋予 r w 两个权限，得到 6（二进制 0b110）

console.log((user & r) === r); // true, 存在 读 权限
console.log((user & w) === w); // true, 存在 写 权限
console.log((user & x) === x); // false, 不存在 执行 权限

用户权限 & 权限 code === 权限 code 可以判断出用户是否拥有该权限。

3. 删除权限

如果想删除某个权限，只需将该权限对应二进制位上的 1 变为 0，按位异或操作符 ^ 可以实现：

let r = 0b100
let w = 0b010
let x = 0b001

let user = r | w; // 赋予 r w 两个权限，得到 6（二进制 0b110）
user = user ^ w;

console.log((user & r) === r); // true, 存在 读 权限
console.log((user & w) === w); // false, 不存在 写 权限
console.log((user & x) === x); // false, 不存在 执行 权限

另一种办法也可以实现删除权限：先按位非取反，再执行按位与操作：&(~code)

let user = r | w; // 赋予 r w 两个权限，得到 6（二进制 0b110）
user = user & (~w); // 0b110 & 0b101 --> 0b100 --> r

console.log((user & r) === r); // true, 存在 读 权限
console.log((user & w) === w); // false, 不存在 写 权限
console.log((user & x) === x); // false, 不存在 执行 权限

四、位运算在 React 源码中的应用 - 标记上下文

React 源码中定义了多个执行上下文，比如渲染阶段 RenderContext 或者提交阶段 CommitContext，在执行函数中会判断当前处于哪个执行环境。

标记上下文场景类似于上面的权限系统，涉及到位运算符操作的场景是：进入某个执行上下文、判断是否处于某个执行上下文、离开某个执行上下文。

假设上下文的种类以下几种，默认的执行上下文为 0：

// A 上下文
const AContext = 0b0001;
// B 上下文
const BContext = 0b0010;
// 初始无上下文
const NoContext = 0b0000;

// 变量记录当前上下文
let context = NoContext;

使用按位或位运算符进入某个上下文

context |= AContext; // 进入 A 执行上下文，得到 0b0001
context |= BContext; // 进入 B 执行上下文，得到 0b0011
console.log(context); // 3

使用按位与位运算符判断是否处于某个上下文

(context & AContext) === AContext; // true 处于 A 执行上下文
(context & BContext) === BContext; // true 处于 B 执行上下文

使用按位非结合按位与（ &(~code) ）离开某个上下文

context &= (~AContext); // 离开 A 执行上下文，得到 0b0010
console.log(context); // 2

五、业务场景 - 记录 change action 修改动作

通常对一个数据列表进行操作时，会涉及添加、修改、删除等动作。

现在业务上需要知道每一个动作，在提交更新时多不同处理，这时候你可能会想到使用三个变量来记录每一个 action 动作。

但如果使用位运算符，只需要有一个变量就能够实现记录这些动作的能力，下面分别为 三个 action 定义二进制值，

// 默认状态
export const NotChanged = 0b0000;
// 记录 数据添加
export const AppendChanged = 0b0001;
// 记录 数据修改
export const UpdateChanged = 0b0010;
// 记录 数据删除
export const DeleteChanged = 0b0100;

在标记动作时，可以这样使用位运算符：

if (changedType === 'not') {
  changed &= NotChanged; // 初始化动作
} else if (changedType === 'append') {
  changed |= AppendChanged; // 标记进行了数据添加操作
} else if (changedType === 'update') {
  changed |= UpdateChanged; // 标记进行了数据更新操作
} else if (changedType === 'delete') {
  changed |= DeleteChanged; // 标记进行了数据删除操作
}

提交数据时判断是否进行了某个操作，可以这样使用位运算符，比如判断是否更新了数据：

if ((changed & UpdateChanged) === UpdateChanged) { ... }

六、位运算算法题 - 只出现一次的数字

题目：给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

比如输入 nums = [4, 1, 2, 1, 2]，输出结果为 4。

解题思路：任意进制的数字在计算机都是将其转化为二进制计算，借助位运算可以来实现。

位运算符 ^ 异或，两个值 bit 位相同为 0，不同为 1，将数组中所有数据进行异或，最后得到的值就是数组中只出现一次的数字。

如示例：[4, 1, 2, 1, 2]，初始值为 0，异或位运算可以理解为：（值第一次出现，异或代表相加，值第二次出现，异或代表相减）

0 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2  --->  4
    ||
0 + 4 + 1 + 2 - 1 - 2  --->  4

代码实现：

function singleNumber(nums) {
  let res = 0;
  nums.forEach(num => {
    res ^= num;
  });
  return res;
}
console.log(singleNumber([4, 1, 2, 1, 2])); // 4