观感度:????????????????????
口味:西南小炒肉
烹饪工夫: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. 点赞、评论、转发 === 催更!