来自小姐姐的灵魂拷问：位运算是什么？

前两天上班，突然小叶给我发消息：哥哥，你看这两段代码是什么意思啊？

乍一看，感觉这代码既熟悉又陌生。好像在哪里见过，但平时好像又很少用到。

我喝口水，冷静的想了 3s：咦，这个不就是那个位运算符吗？之前大学就学过，前一段看react源码也有看到过啊！

小叶：哥哥，那你能不能给我讲一下这是什么呢？

我：没问题，等我整理一下～

什么是位运算？

位运算简单来说就是基于整数的二进制表示进行的运算。它直接处理每一个比特位，是非常底层的运算，好处是速度极快，缺点是不太直观。

你这会可能会问：二进制是什么？

哈哈，其实如果不是科班出身的同学，对二进制有点陌生也正常了。下面我就简短的介绍一下二进制。

我们常用的 2、8、16 等数字是十进制表示，而位运算的基础是二进制。即人类采用十进制，机器采用的是二进制，要深入了解位运算，就需要了解十进制和二进制的转换方法和对应关系。

十进制转二进制

十进制整数转换为二进制整数采用除2取余，逆序排列法。具体做法是：用 2 整除十进制整数，可以得到一个商和余数；再用 2 去除商，又会得到一个商和余数，如此进行，直到商为小于 1 时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

这里以十进制数 156 为例：

二进制转十进制

小数点前或者整数要从右到左用二进制的每个数去乘以 2 的相应次方并递增,小数点后则是从左往右乘以二的相应负次方并递减。

这里以 1011.01 为例：

介绍完了二进制和十进制的相互转换，下面我们就来看下在js中经常用到的几个位运算符吧。

JS 中常用的 7 个位运算符

基本的位运算共 7 种，分别为

• 按位与(AND) &
• 按位或(OR) |
• 按位异或(XOR) ^
• 按位非(NOT) ~
• 左移（Left shift）<<
• 有符号右移>>
• 无符号右移>>>

这里用一个表格来汇总下以上 7 种运算符的简介：

运算符用法描述按位与(AND) &a & b对于每一个比特位，只有两个操作数相应的比特位都是 1 时，结果才为 1，否则为 0。`按位或(OR)`ab对于每一个比特位，当两个操作数相应的比特位至少有一个 1 时，结果为 1，否则为 0。按位异或(XOR) ^a ^ b对于每一个比特位，当两个操作数相应的比特位有且只有一个 1 时，结果为 1，否则为 0。按位非(NOT) ~~a反转操作数的比特位，即 0 变成 1，1 变成 0。左移（Left shift）<<a << b将 a 的二进制形式向左移 b (< 32) 比特位，右边用 0 填充。有符号右移>>a >> b将 a 的二进制表示向右移 b (< 32) 位，丢弃被移出的位。无符号右移>>>a >>> b将 a 的二进制表示向右移 b (< 32) 位，丢弃被移出的位，并使用 0 在左侧填充。

按位与(AND) &

&运算符（位与）用于对两个二进制操作数逐位进行比较。如果对应的位都为 1，那么结果就是 1， 如果任意一个位是 0 则结果就是 0。

按位或(OR) |

｜运算符（位或）用于对两个二进制操作数逐位进行比较。只要两个对应位中有一个 1 时就为 1，否则为 0。

按位异或(XOR) ^

^运算符（位异或）用于对两个二进制操作数逐位进行比较。只有两个对应位不同时才为 1。

按位非(NOT) ~

~运算符（位非）用于对两个二进制操作数逐位进行比较。对位求反，1 变 0, 0 变 1。

这里稍微有些麻烦，做下解释：1 反码二进制表示: 11111111 11111111 11111111 11111110。由于第一位（符号位）是 1，所以这个数是一个负数。JavaScript 内部采用补码形式表示负数，即需要将这个数减去 1，再取一次反，然后加上负号，才能得到这个负数对应的 10 进制值。

1 的反码减 1 为：11111111 11111111 11111111 11111101。

反码取反：00000000 00000000 00000000 00000010。再加上符号位-。最终得到 1 的按位非为-2。

二进制数的负数是取该二进制数的补码,然后+1。二进制数,最高位为 0 表示正数,最高位为 1 表示负数。~按位非操作其实就是取补码的过程,也就是上述求该值负数的逆过程,所以可以简单的理解为该值取负值后减 1。

这里其实是有一个小技巧的：一个数与自身的取反值相加等于-1。

左移（Left shift）<<

<<运算符（左移）表示将指定的二进制向左移动指定的位数。

有符号右移>>

>>运算符（右移）表示将指定的二进制向右移动指定的位数。

在MDN上你可以看到：

这句话最后一句提到了"sign-propagating"，中文翻译过来就是符号传播的意思，为什么这样说呢：我们知道，计算机中以二进制存储数字，二进制中最左边的第一位，叫符号位，所以这就很明显了，右移 2 位后，最左边缺少 2 位数字，那就应该填充数字，那填充什么呢？符号位是什么，我就填什么。由于新的最左侧的位总是和以前相同，符号位没有被改变。所以被称作“符号传播”。

无符号右移>>>

很多同学可能会对>>>和>>的区别很好奇，同样我们来看MDN上对无符号右移>>>的解释：

同样，有一个核心词语：zero-fill right shift。翻译过来就是零-填充，这个就更明显了，右移后空位不管你符号位是什么，我都只填 0。

这里就可以得到一个结论：对于非负数，有符号右移和无符号右移总是返回相同的结果。

到这里，JS 中常用的 7 个位运算符的介绍就差不多了。下面让我们来看下React中对于按位运算符的使用场景。（毕竟这是我第一次在实际的业务场景中看到有人用按位运算符的）

React 当中的使用场景

EffectTag

我们知道每一个 React元素对应一个 fiber对象，一个 fiber 对象通常是表征 work的一个基本单元：

// packages/react-reconciler/src/ReactFiber.js

// A Fiber is work on a Component that needs to be done or was done. There can
// be more than one per component.
export type Fiber = {
// 标识 fiber 类型的标签
    tag: WorkTag,

    // 指向父节点
    return: Fiber | null,

    // 指向子节点
    child: Fiber | null,

    // 指向兄弟节点
    sibling: Fiber | null,

    // 在开始执行时设置 props 值
    pendingProps: any,

    // 在结束时设置的 props 值
    memoizedProps: any,

    // 当前 state
    memoizedState: any,

    // Effect 类型，详情查看以下 effectTag
    effectTag: SideEffectTag,

    // effect 节点指针，指向下一个 effect
    nextEffect: Fiber | null,

    // effect list 是单向链表，第一个 effect
    firstEffect: Fiber | null,

    // effect list 是单向链表，最后一个 effect
    lastEffect: Fiber | null,

    // work 的过期时间，可用于标识一个 work 优先级顺序
    expirationTime: ExpirationTime,
};

每一个fiber节点都有一个和它相关联的 effectTag值。
我们把不能在 render 阶段完成的一些 work 称之为副作用，React罗列了可能存在的各类副作用，如下所示：

// packages/shared/ReactSideEffectTags.js

export type SideEffectTag = number;

// Don't change these two values. They're used by React Dev Tools.
export const NoEffect = /*              */ 0b000000000000;
export const PerformedWork = /*         */ 0b000000000001;

// You can change the rest (and add more).
export const Placement = /*             */ 0b000000000010;
export const Update = /*                */ 0b000000000100;
export const PlacementAndUpdate = /*    */ 0b000000000110;
export const Deletion = /*              */ 0b000000001000;
export const ContentReset = /*          */ 0b000000010000;
export const Callback = /*              */ 0b000000100000;
export const DidCapture = /*            */ 0b000001000000;
export const Ref = /*                   */ 0b000010000000;
export const Snapshot = /*              */ 0b000100000000;
export const Passive = /*               */ 0b001000000000;

// Passive & Update & Callback & Ref & Snapshot
export const LifecycleEffectMask = /*   */ 0b001110100100;

// Union of all host effects
export const HostEffectMask = /*        */ 0b001111111111;

export const Incomplete = /*            */ 0b010000000000;
export const ShouldCapture = /*         */ 0b100000000000;

可以看到大部分的值都只有一位是 1，其他位都是 0。

0bxxx是原生二进制字面量的表示方法

这里列举一个用到effectTag的场景：

• (workInProgress.effectTag & DidCapture) !== NoEffect

这里其实是对二进制做与运算：我们拿Update和DidCapture来进行&操作，那么得到的结果就很明显了，所有位都是 0。

所以这里的&操作就是用来判断在某个变量中是否含有某个属性的。比如这里就是判断workInProgress.effectTag中是否含有DidCapture这个属性。

相应的位运算场景在 react 源码中还有很多很多，这里就不一一说明了。下面来看下在实际的业务开发中，位运算比较常用的场景。

位运算符在 JS 中的妙用

切换变量 0 或 1

平时我们做一些变量状态的切换，多半会这样去写：

if (flag) {
    flag = 0;
} else {
    flag = 1;
}

或者简写为：

flag = flag ? 0 : 1;

如果用位运算来实现的话：

toggle ^= 1;

有没有感觉很简单～

使用&运算符判断一个数的奇偶

相比与 2 取余的方式，这种方式也比较简洁：

// 偶数 & 1 = 0
// 奇数 & 1 = 1
console.log(2 & 1)    // 0
console.log(3 & 1)    // 1

交换两个数(不能使用额外的变量)

交换两个整数的值，最直观的做法是借助一个临时变量：

let a = 5,
  b = 6
// 交换a, b的值
let c = a
a = b
b = c

现在要求不能使用额外的变量或内容空间来交换两个整数的值。这个时候就得借助位运算，使用异或可以达到这个目的：

let a = 5,
  b = 6;

a = a ^ b; // 3
b = a ^ b; // 5
a = a ^ b; // 6

如果你没看明白，那我们分开来分析一下。

首先：a = a ^ b，即a = 0101 ^ 0110 = 0011 = 3；

第二步：b = a ^ b，即b = 0011 ^ 0110 = 0101 = 5；

最后：a = a ^ b，即a = 0011 ^ 0101 = 0110 = 6。

至此，没有使用额外的变量完成了两个整数值的交换。

有关 2 的幂的应用

这块我在刷leetcode时深有体会下面一起来看下吧：

比较常规的，就是不断除以 2，判断最终结果是否为 1，也就是采用递归的方法。

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function(n) {
    if (n < 1){
        return false;
    }
    if (n == 1) {
        return true;
    }
    if (n % 2 > 0) {
        return false;
    }
    return isPowerOfTwo(n / 2);
};

我们考虑一下有没有更快的解决方式：观察 2^0、2^1、2^2......2^n，它们的二进制表示为 1、10、100、1000、10000......

判断一个数是否是 2 的 n 次幂，也就是判断二进制表示中是否只有一位是 1 且在最前面那位的位置。例如 n=00010000，那 n-1=00001111，即n&(n-1)==0

由此就可以判断啦！

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function(n) {
    return n > 0 && (n & (n-1)) === 0
};

位 1 的个数

这里有一个小技巧， 可以轻松求出。 就是n & (n - 1) 可以消除 n 最后的一个 1。

如果对位运算比较了解的话，那么相信你一定对上述这条skill很熟悉 ?

这样我们可以不断进行n = n & (n - 1)直到n === 0 ， 说明没有一个 1 了。通过count去计数即可～

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    let count = 0;
    while (n !== 0) {
        // n & (n - 1) 可以消除 n 最后的一个1
        n = n & (n-1)
        count++
    }
    return count
};

权限系统设计

后台管理系统中控制不同用户的操作权限是一种很常见的行为。通常我们会采用数组的方式来表示某种用户所拥有的操作权限：

roles: ["admin", "editor"],

设想如果我们采用位运算来设计这个权限系统：

• 管理员（一级权限）：0b100
• 开发（二级权限）：0b010
• 运营（三级权限）：0b001

如果 A 操作只能由管理员和开发操作，那么这个权限值表示为6 = 0b110，它和管理员权限&一下：6 & 4 = 0b110 & 0b100 = 4，得到的值不为 0，所以认为有权限。同理和开发权限&一下6 & 2 = 2也不为 0，而与运营权限&一下6 & 1 = 0，所以运营没有权限。

这样的好处在于，我们可以用一个数字，而不是一个数组来表示某个操作的权限集，同时在进行权限判断的时候也很方便。

本篇对位运算做了一个较为系统的说明。其实在实际的开发中，不了解位元算的同学也不少。但是在某些场景下能合理的运用位运算也是可以解决很多实际问题的。