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

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

react

乍一看，感受这代码既熟悉又陌生。好像在哪里见过，但平时好像又不多用到。
数组

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

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

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

什么是位运算？

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

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

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

二进制

咱们经常使用的 二、八、16 等数字是十进制表示，而位运算的基础是二进制。即人类采用十进制，机器采用的是二进制，要深刻了解位运算，就须要了解十进制和二进制的转换方法和对应关系。code

十进制转二进制

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

这里以十进制数 156 为例：

二进制转十进制

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

这里以 1011.01 为例：

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

JS 中经常使用的 7 个位运算符

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

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

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

按位与(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 的幂

比较常规的，就是不断除以 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^一、2^2......2^n，它们的二进制表示为 一、十、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，因此运营没有权限。

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

总结

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