位操作及其应用

jiezi

5 年前

我在看 lodash 实现一些工具函数的源码时发现 lodash 定义了一些 bitMask 的常量。我一开始没弄明这是什么鬼东西，用 Google 搜了一圈才发现是我之前接触过得位操作运算一类的东西。并且源码和我搜索的资料给我提供了另一种使用场景，感觉应用性还是蛮强的，所以干脆总结一下好了。

先以下面的表达式展开需要了解的基础知识。

// lodash 源码里定义的常量
var CLONE_DEEP_FLAG = 1

JavaScript 遵循 IEEE 754 标准，无论是整数还是小数都是用双精度浮点数表述，双精度浮点数 8 个字节，表示 64 位二进制位，所以双精度浮点数的表示范围是-2^63 ~ 2^63-1。但是在进行位操作时则是用的 32 位数表示，也就是 4 个字节，表示范围为 `-2^31 ~ 2^31-1，其中无论是 32 位还是 64 位，最高位都是符号位，0 表示正数，1 表示负数。

上面的表达式在进行位操作就会转换成下面这种，如果超过 32 位了，那超过的部分就会全部省去。

00000000 00000000 00000000 00000001

下面介绍几种常用的操作符。

let a = 1,
    b = 2
    
console.log(a & b) // 0

// 0001
// 0010
// = 0000

把变量 a 和变量 b 都展开成 32 位二进制数，省去前面的 0，a的二进制表示为 0001，b 为0010，接着就是对应位数的二进制位比较，如果相同就是 1，否则为 0。

let a = 1,
    b = 2
    
console.log(a | b) // 3

// 0001
// 0010
// = 0011

参照上面一种，不同的是相同的二进制位上，只要有一个是 1，则结果就是 1，所以就是0011。

这个和 | 有点区别，相同的地方在于如果同一位数上的数只要一个是 1，则这个位数的结果就是 1，不同的地方在于相同的位数上如果数值相同，则结果为 0.

let a = 1,
    b = 2
    
console.log(a ^ b) // 3

// 0001
// 0010
// = 0011

let c = 3,
    d = 3
    
console.log(a ^ b) // 0

// 0011
// 0011
// = 0000

这个和之前三个最大的区别是对单个数的操作，而不是两个数的比较结果。简单来说就是取反，对二进制上的每一位都取反。但是这里有个有趣的现象。

let a = 1;

console.log(~ a) // -2

无论用 ~ 取反任何数，得出的都是负数，而且是在正数上加一的负数。这里涉及三个概念：原码 ， 反码 ， 补码 。首先明确一点， 负数是以补码的形式存在的。

正数和负数的都是转换成二进制数后的样子，不同的是负数的原码在最高位 +1。

// 4 的原码
00000000 000000000 000000000 00000100
// - 4 的原码
10000000 000000000 000000000 00000100

正数的反码和正数的原码一致。但负数的反码是对除了符号位上的其他二进制位取反。

// 4 的反码
00000000 000000000 000000000 00000100
// - 4 的反码
11111111 11111111 11111111 11111011

正数的补码还是和正数的原码一致，但负数的补码是在负数反码的基础上对最后一位加 1。

// 4 的补码
00000000 000000000 000000000 00000100
// - 4 的补码
11111111 11111111 11111111 11111100

所以说回上面提到的问题，3 被 ~ 转换为 -4 的过程。

3：00000000 00000000 00000000 00000100
~3：11111111 11111111 11111111 11111011

// ~3 这时候表示的是负数，那就按照原码 -> 补码的顺序倒推 
// 1. 最低的位数 -1
 11111111 11111111 11111111 11111010 
// 2. 取反（除了符号位）10000000 00000000 00000000 00000101
// 3. 转换成十进制
-4

介绍完了几种操作符，来说说有啥应用。

这是 LeetCode 上的一道题，题目是这样写的：

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

这个用上面介绍过的 ^(异或) 操作符是最容易解答的，可以可以下 ^ 的特性。题目里说的是只有一个数是唯一的，其他都是两两出现，而相同的数字，就像我上面举例用了两个 3，结果是 0，因为每个二进制上的数都相同，所以结果就是每个位上都变成了 0.

function onlyNums(arr){return arr.reduce((all,item) => all ^ item)
}

这个例子就和我们的日常贴的比较近了。后台系统进行权限配置的时候，一般可能就是定义几个字符串定义不同的权限，如果一个人同时有很多权限，结果可能是个数组，也可能是把不同权限字符串拼接成新的字符串。

let permission1 = 001 // 登录权限
let permission2 = 002 // 创建权限
let permission3 = 003 // 删除权限
let adminPermission = '001,002,003'
// or
let adminPermission = [001,002,003]

如果换成位操作的思路：

let permission1 = 1 // 登录权限
let permission2 = 2 // 创建权限
let permission3 = 4 // 删除权限
let permission4 = 8 // 编辑权限

let adminPermission = (permission1 | permission2 | permission3)

这个时候检查 adminPermission 是否拥有某个权限就可以这样：

if((adminPermission & permission1) === permission1){// 有登录权限}

删除某个权限：

adminPermission = adminPermission & (~ permission2)

新增某个权限：

adminPermission = adminPermission | permission4

除了上面两种场景，位操作还用于加密算法中，但是我的工作没有涉及过这方面，所以就不具体展开说了。感兴趣的话可以自己看看。

位操作及其应用

&（位与）

|（位或）

^（位异或）

~（位异或）

原码

反码

补码

应用

136. 只出现一次的数字

权限