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

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

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

我喝口水，沉着的想了 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.jsexport 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 & Snapshotexport const LifecycleEffectMask = /*   */ 0b001110100100;// Union of all host effectsexport 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 = 1console.log(2 & 1)    // 0console.log(3 & 1)    // 1

替换两个数(不能应用额定的变量)

替换两个整数的值，最直观的做法是借助一个长期变量：

let a = 5,  b = 6// 替换a, b的值let c = aa = bb = c

当初要求不能应用额定的变量或内容空间来替换两个整数的值。这个时候就得借助位运算，应用异或能够达到这个目标：

let a = 5,  b = 6;a = a ^ b; // 3b = a ^ b; // 5a = 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，所以经营没有权限。

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

总结

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