关于面试:来自小姐姐的灵魂拷问位运算是什么

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

乍一看，感觉这代码既相熟又生疏。如同在哪里见过，但平时如同又很少用到。

我喝口水，沉着的想了 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) &

&运算符（位与）用于对两个二进制操作数逐位进行比拟。如果对应的位都为 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^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，所以经营没有权限。

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

总结

本篇对 位运算 做了一个较为零碎的阐明。其实在理论的开发中，不理解 位元算 的同学也不少。然而在某些场景下能正当的使用 位运算 也是能够解决很多理论问题的。