共计 5455 个字符，预计需要花费 14 分钟才能阅读完成。
观感度：????????????????????
口味：西南小炒肉
烹饪工夫：10min
本文已收录在前端食堂同名仓库 Github github.com/Geekhyt，欢迎光临食堂，如果感觉酒菜还算可口，赏个 Star 对食堂老板来说是莫大的激励。
初识位运算
记忆
&，与两个位都为 1 时，后果才为 1|，或两个位都为 0 时，后果才为 0^，异或两个位雷同为 0，相异为 1～，按位取反所有 0 变 1，1 变 0<<，左移各二进位全副左移若干位，高位抛弃，低位补 0>>，右移各二进位全副右移若干位，对无符号数，高位补 0，有符号数，各编译器解决办法不一样，有的补符号位，有的补 0
了解
其实很简略，小学数学题难度，花几分钟看完如果看懂了请点个赞呗。
左移
二进制左移一位，就是将数字翻倍。
二进制 110101 向左移一位，就是在开端增加一位 0，也就是 1101010。(此处探讨的是数字没有溢出的状况)
二进制 110101 转化成十进制：
1 2^5 + 1 2^4 + 0 2^3 + 1 2^2 + 0 2^1 + 1 2^0
= 32 + 16 + 0 + 4 + 0 + 1
= 53
二进制 1101010 转化成十进制：
1 2^6 + 1 2^5 + 0 2^4 + 1 2^3 + 0 2^2 + 1 2^1 + 0 * 2^0
= 64 + 32 + 0 + 8 + 0 + 2 + 0
= 106
右移
二进制右移一位，就是将数字除以 2 并求整数商。
二进制 110101 向右移一位，就是去除掉开端的那一位，也就是 11010。
二进制 11010 转化成十进制：
1 2^4 + 1 2^3 + 0 2^2 + 1 2^1 + 0 * 2^0
= 16 + 8 + 0 + 2 + 0
= 26
无符号右移和有符号右移（逻辑右移和算术右移）
无符号右移应用 >>> 示意，而有符号右移应用 >> 示意。
>>> 无符号右移 1 位，左边抛弃，右边补 0 即可。
>> 有符号右移保留符号，拷贝最左侧的位来填充左侧，向右位移并抛弃最左边的位。
因为左移位无需思考高位补 1 还是补 0（符号位可能为 1 或 0），所以不须要辨别无符号左移和有符号左移。
位的或
参加操作的位中只有有一个位是 1，那么最终后果就是 1。
如果咱们将 110101 和 100011 进行按位的或操作，就会失去 110111。
位的与
参加操作的位中必须都是 1，最终后果才是 1，否则为 0。
如果咱们将 110101 和 100011 进行按位的与操作，就会失去 100001。
位的异或
参加操作的位雷同，最终后果是 0，否则为 1。
想要失去 1，参加操作的两个位必须不雷同，也就是异或中“异”的含意。
如果咱们将 110101 和 100011 进行按位的异或操作，就会失去 10110。
罕用公式
判断奇偶
x % 2 === 1 -> (x & 1) === 1 (奇数)
x % 2 === 0 -> (x & 1) === 0 (偶数)
x >> 1 -> x / 2
即：x = x / 2; -> x = x >> 1;
mid = (left + right) / 2; -> mid = (left + right) >> 1;
x = x & (x – 1)
清零最低位的 1，代表将最初一位 1 变成 0。
x & -x
失去最低位的 1，代表除最初一位 1 保留，其余位全副为 0。
将 x 最左边的 n 位清零
x & (~0 << n)
获取 x 的第 n 位值
(x >> n) & 1
获取 x 的第 n 位的幂值
x & (1 << (n - 1))
仅将第 n 地位为 1
x | (1 << n)
仅将第 n 地位为 0
x & (~(1 << n))
将 x 最高位至第 n 位 (含) 清零
x & ((1 << n) - 1)
将第 n 位至第 0 位 (含) 清零
x & (~((1 << (n + 1)) - 1))
Leecode 真题解析 N 皇后 II
- 原题链接
n 皇后问题钻研的是如何将 n 个皇后搁置在 n×n 的棋盘上，并且使皇后彼此之间不能互相攻打。
(图片起源 LeeCode，同上原题链接)
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例:
输出: 4
输入: 2
解释: 4 皇后问题存在如下两个不同的解法。[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]提醒：
- 皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见能够吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一或 N-1 步，可进可退。（援用自 百度百科 – 皇后）
了解
皇后能够横、直、斜走，格数不限。题目要求皇后彼此之间不能互相攻打，也就是说须要满足任意两个皇后不能在同一行、同一列以及同一条斜线上。
相熟这道题的同学，能够看出最直观的做法是利用回溯法进行求解。
遍历枚举出所有可能的抉择，顺次在每一行搁置一个皇后，每次新搁置的皇后不能和曾经搁置的皇后之间存在攻打。
为了升高工夫复杂度，最现实的状况是在 O(1) 的工夫内判断该地位所在的几条线上是否曾经有皇后，能够利用汇合来进行地位判断。
为了让你更好的了解，我利用回溯法将 4 皇后可能的解法画了进去。如下图所示：
一句话了解四种算法思维
分治：分而治之，先解决子问题，再将子问题的解合并求出原问题。贪婪：一条路走到黑，抉择当下部分最优的路线，没有后悔药。回溯：一条路走到黑，手握后悔药，能够无数次重来。(英雄联盟艾克大招无冷却)。动静布局：上帝视角，手握有数平行宇宙的历史存档，同时倒退出无数个将来。
上面这张图是两条对角线方向的斜线的法则，聪慧的你必定一眼就能看进去：
解法一 汇合回溯
如下所示是官网给出的题解：
const backtrack = (n, row, columns, diagonals1, diagonals2) => {if (row === n) {return 1;} else {
let count = 0;
for (let i = 0; i < n; i++) {if (columns.has(i)) {continue;}
const diagonal1 = row - i;
if (diagonals1.has(diagonal1)) {continue;}
const diagonal2 = row + i;
if (diagonals2.has(diagonal2)) {continue;}
columns.add(i);
diagonals1.add(diagonal1);
diagonals2.add(diagonal2);
count += backtrack(n, row + 1, columns, diagonals1, diagonals2);
columns.delete(i);
diagonals1.delete(diagonal1);
diagonals2.delete(diagonal2);
}
return count;
}
}
const totalNQueens = function(n) {const columns = new Set();
const diagonals1 = new Set();
const diagonals2 = new Set();
return backtrack(n, 0, columns, diagonals1, diagonals2);
};- 工夫复杂度：O(N!)
- 空间复杂度：O(N)
解法二 位运算回溯
学会了位运算，你能够将代码写的更加优雅。
先来明确几个概念和须要用到的公式：
n：n 层row：以后层cols：列pie：撇，左斜线(副对角线)na：捺，右斜线(正对角线)二进制为 1，代表不可搁置，0 相同x & -x：失去最低位的 1 (代表除最初一位 1 保留，其余位全副为 0)x & (x - 1)：清零最低位的 1 (代表将最初一位 1 变成 0)x & ((1 << n) - 1)：将 x 的最高位至第 n 位 (含) 清零
思路
将 N 个地位对应成 N 个二进制位，0 代表能够抉择，1 代表不能抉择。比方八皇后以后第一行的第二位被抉择时的状态是 00100000，那么下一行的第二位也不能被抉择，正对角线 (na) 对应的第三位不能被抉择 (对该当前行右移了一位)，状态示意为：00100000。副对角线(pie) 对应的第一位不能被抉择(对该当前行左移了一位)，状态示意为 10000000。
const totalNQueens = function(n) {
let res = 0;
const dfs = (n, row, cols, pie, na) => {if (row >= n) {
res++;
return;
}
let bits = (~(cols | pie | na)) & ((1 << n) - 1) // 1
while (bits) { // 2
let p = bits & -bits // 3
dfs(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1) // 4
bits = bits & (bits - 1) // 5
}
}
dfs(n, 0, 0, 0, 0);
return res;
};- 工夫复杂度：O(N!)
- 空间复杂度：O(N)
代码解读
1.cols | pie | na 示意所有可能被皇后攻打的格子，~(cols | pie | na)取反示意将没有被占的格子从 0 变为 1，以便后续的位遍历。这里用到 公式：x & ((1 << n) - 1)：将 x 的最高位至第 n 位 (含) 清零。一个 int 的二进制位至多有 32 位，咱们将后面不须要的地位清零。所以，这行代码示意失去以后所有的空位，也就是能够搁置皇后的格子。
2. 只有 bits 中有 1，就阐明还有格子能够搁置皇后，每次遍历都会将其清零 (示意在 p 地位放入了皇后)，也就是正文 5 的代码含意。对应 公式：x & (x - 1)：清零最低位的 1 (代表将最初一位 1 变成 0)。
3. 对应 公式：x & -x：失去最低位的 1 (代表除最初一位 1 保留，其余位全副为 0)，示意以后皇后可放入的地位。
4. 批改状态，进入下一层递归。row + 1 代表搜寻下一行，cols | p 代表目前所有能够搁置皇后的列。(pie | p) << 1，(na | p) >> 1，在下面思路中曾经说过了，不再赘述。
Vue3 中的位运算之 shapeFlags、patchFlags
Vue3 中也有一些对于位运算的实际。
shapeFlags
shapeFlags 针对 VNode 的 type 进行了更具体的分类，便于在 patch 阶段，依据不同的类型执行相应的逻辑。
能够点击此处跳转到源码仓库进行查看
// packages/shared/src/shapeFlags.ts
export const enum ShapeFlags {
ELEMENT = 1, // HTML 或 SVG 标签 一般 DOM 元素
FUNCTIONAL_COMPONENT = 1 << 1, // 函数式组件
STATEFUL_COMPONENT = 1 << 2, // 一般有状态组件
TEXT_CHILDREN = 1 << 3, // 子节点是纯文本
ARRAY_CHILDREN = 1 << 4, // 子节点是数组
SLOTS_CHILDREN = 1 << 5, // 子节点是插槽
TELEPORT = 1 << 6, // Teleport
SUSPENSE = 1 << 7, // Suspense
COMPONENT_SHOULD_KEEP_ALIVE = 1 << 8, // 须要被 keep-alive 的有状态组件
COMPONENT_KEPT_ALIVE = 1 << 9, // 曾经被 keep-alive 的有状态组件
COMPONENT = ShapeFlags.STATEFUL_COMPONENT | ShapeFlags.FUNCTIONAL_COMPONENT // 有状态组件和函数组件都是组件，用 COMPONENT 示意
}patchFlags
patchFlags 用于标识节点更新的类型，用于运行时优化。
// packages/shared/src/patchFlags.ts
export const enum PatchFlags {
TEXT = 1, // 动静文本节点
CLASS = 1 << 1, // 动静 class
STYLE = 1 << 2, // 动静 style
PROPS = 1 << 3, // 动静属性
FULL_PROPS = 1 << 4, // 具备动静 key 属性，当 key 扭转时，须要进行残缺的 diff 比拟
HYDRATE_EVENTS = 1 << 5, // 具备监听事件的节点
STABLE_FRAGMENT = 1 << 6, // 子节点程序不会被扭转的 fragment
KEYED_FRAGMENT = 1 << 7, // 带有 key 属或局部子节点有 key 的 fragment
UNKEYED_FRAGMENT = 1 << 8, // 子节点没有 key 的 fragment
NEED_PATCH = 1 << 9, // 非 props 的比拟，比方 ref 或指令
DYNAMIC_SLOTS = 1 << 10, // 动静插槽
DEV_ROOT_FRAGMENT = 1 << 11, // 仅供开发时应用，示意将正文放在模板根级别的片段
HOISTED = -1, // 动态节点
BAIL = -2 // diff 算法要退出优化模式
}通过进行 | 或运算进行标记的组合，如果以后节点是一个动静文本节点(0000 0001)，它同时又具备动静 style (0000 0100)，二者进行 | 或运算后值为 (0000 0101)。
通过进行 & 与运算进行标记的查看。能够点击此处跳转到源码仓库进行查看
读这部分正文的时候发现了援用文件门路的谬误，提交了 Pr，胜利混入了 Vue Contributor，与尤大进行了一波密切互动。
所以说，好好学习是有回报的，一起加油吧，打工人！
如果你对 Vue3 DOM Diff 外围算法感兴趣的话，也欢送浏览我的另外一篇专栏，Vue3 DOM Diff 外围算法解析
更有其余算法系列专栏，让你一次看过瘾：
- 前端如何搞定数据结构与算法(先导篇)
- 「工夫治理」JavaScript 算法工夫、空间复杂度剖析
- 你真的懂递归吗？
- 分治、动静布局、回溯、贪婪一锅炖
- 「种树专业户」“树”业有专攻
- 从酒桌游戏看二分查找算法
- 面试链表不再怕
- 食堂店小二儿教你学会栈
❤️爱心三连击
1. 如果你感觉食堂酒菜还合胃口，就点个赞反对下吧，你的 赞是我最大的能源。
2. 关注公众号前端食堂，吃好每一顿饭！
3. 点赞、评论、转发 === 催更！
