0b1000=2*2*2=Math.pow(2,3)=8=0~7
运算 | 使用 | 说明 |
---|---|---|
按位与(&) | x & y | 每一个比特位都为1时,结果为1,否则为0 |
按位或() | x y | 每一个比特位都为0时,结果为0,否则为1 |
按位异或(^) | x ^ y | 每一个比特位相同结果为0,否则为1 |
按位非(~) | ~ x | 对每一个比特位取反,0变为1,1变为0 |
左移(<<) | x << y | 将x的每一个比特位左移y位,右侧补充0 |
有符号右移(>>) | x >> y | 将x的每一个比特位向右移y个位,右侧移除位丢弃,左侧填充为最高位 |
无符号右移(>>>) | x >>> y | 将x的每一个比特位向右移y个位,右侧移除位丢弃,左侧填充为0 |
let a = 0b100;//4
let b = 0b011;//3
console.log((a & b).toString(2));//000 0
console.log((a | b).toString(2));//111 7
console.log((a ^ b).toString(2));//111 7
//按位非运算时,任何数字x的运算结果都是-(x + 1)。例如,〜4运算结果为-5
console.log((~a));//-5
console.log((~a).toString(2));//111
let a = 0b001;
//左移
console.log((a << 2).toString(2));// 0b100
//无符号右移(>>>) 丢弃被移除的位 左侧补0
let b = 0b100;
console.log((b >>> 1).toString(2));// 0b010
//有符号右移(>>) 丢弃被移除的位 左侧填充最高位
let c = 0b101;//-3 110
console.log((-3 >> 1));
//定义常量
const OP_INSERT = 1 << 0; // 0b001
const OP_REMOVE = 1 << 1; // 0b010
let OP = 0b000;
//增加操作
OP |= OP_INSERT;
OP |= OP_REMOVE;
console.log(OP.toString(2));//0b11
//删除操作
OP = OP & ~OP_INSERT;
console.log(OP.toString(2));//0b10
//判断包含
console.log((OP & OP_INSERT) === OP_INSERT);
console.log((OP & OP_REMOVE) === OP_REMOVE);
//判断不包含
console.log((OP & OP_INSERT) === 0);
console.log((OP & OP_REMOVE) === 0);
//一共有16种优先级
//同步优先级
const SyncLanePriority = 15;
const SyncBatchedLanePriority = 14;
//离散事件优先级
const InputDiscreteHydrationLanePriority = 13;
const InputDiscreteLanePriority = 12;
//连续事件优先级
const InputContinuousHydrationLanePriority = 11;
const InputContinuousLanePriority = 10;
//默认优先级
const DefaultHydrationLanePriority = 9;
const DefaultLanePriority = 8;
//渐变优先级
const TransitionHydrationPriority = 7;
const TransitionPriority = 6;
const RetryLanePriority = 5;
const SelectiveHydrationLanePriority = 4;
//空闲优先级
const IdleHydrationLanePriority = 3;
const IdleLanePriority = 2;
//离屏优先级
const OffscreenLanePriority = 1;
//未设置优先级
const NoLanePriority = 0;
/**
* 一共有31条车道
*/
const TotalLanes = 31;
//没有车道,所有位都为0
const NoLanes = 0b0000000000000000000000000000000;
const NoLane = 0b0000000000000000000000000000000;
//同步车道,优先级最高
const SyncLane = 0b0000000000000000000000000000001;
const SyncBatchedLane = 0b0000000000000000000000000000010;
//离散用户交互车道 click
const InputDiscreteHydrationLane = 0b0000000000000000000000000000100;
const InputDiscreteLanes = 0b0000000000000000000000000011000;
//连续交互车道 mousemove
const InputContinuousHydrationLane = 0b0000000000000000000000000100000;
const InputContinuousLanes = 0b0000000000000000000000011000000;
//默认车道
const DefaultHydrationLane = 0b0000000000000000000000100000000;
const DefaultLanes = 0b0000000000000000000111000000000;
//渐变车道
const TransitionHydrationLane = 0b0000000000000000001000000000000;
const TransitionLanes = 0b0000000001111111110000000000000;
//重试车道
const RetryLanes = 0b0000011110000000000000000000000;
const SomeRetryLane = 0b0000010000000000000000000000000;
//选择性水合车道
const SelectiveHydrationLane = 0b0000100000000000000000000000000;
//非空闲车道
const NonIdleLanes = 0b0000111111111111111111111111111;
const IdleHydrationLane = 0b0001000000000000000000000000000;
//空闲车道
const IdleLanes = 0b0110000000000000000000000000000;
//离屏车道
const OffscreenLane = 0b1000000000000000000000000000000;
/**
* 分离出所有比特位中最右边的1
* 分离出最高优先级的车道
* @param {*} lanes 车道
* @returns 车道
*/
function getHighestPriorityLane(lanes) {
return lanes & -lanes;
}
//console.log(getHighestPriorityLane(InputDiscreteLanes));//8 0b1000
//console.log('0000000000000000000000000011000');
//console.log('1111111111111111111111111101000');
/**
* 分离出所有比特位中最左边的1
* 分离出最低优先级的车道
* @param {*} lanes 车道
* @returns 车道
*/
function getLowestPriorityLane(lanes) {
const index = 31 - Math.clz32(lanes);
return index < 0 ? NoLanes : 1 << index;
}
console.log(getLowestPriorityLane(InputDiscreteLanes));//16 0b10000
console.log('0000000000000000000000000011000');
console.log(Math.clz32(InputDiscreteLanes));//27
console.log(31 - Math.clz32(InputDiscreteLanes));//4
siftDown
函数向下调整堆siftUp
函数向上调整堆react\packages\scheduler\src\SchedulerMinHeap.js
export function push(heap, node) {
const index = heap.length;
heap.push(node);
siftUp(heap, node, index);
}
export function peek(heap) {
const first = heap[0];
return first === undefined ? null : first;
}
export function pop(heap) {
const first = heap[0];
if (first !== undefined) {
const last = heap.pop();
if (last !== first) {
heap[0] = last;
siftDown(heap, last, 0);
}
return first;
} else {
return null;
}
}
function siftUp(heap, node, i) {
let index = i;
while (true) {
const parentIndex = index - 1 >>> 1;
const parent = heap[parentIndex];
if (parent !== undefined && compare(parent, node) > 0) {
heap[parentIndex] = node;
heap[index] = parent;
index = parentIndex;
} else {
return;
}
}
}
function siftDown(heap, node, i) {
let index = i;
const length = heap.length;
while (index < length) {
const leftIndex = (index + 1) * 2 - 1;
const left = heap[leftIndex];
const rightIndex = leftIndex + 1;
const right = heap[rightIndex];
if (left !== undefined && compare(left, node) < 0) {
if (right !== undefined && compare(right, left) < 0) {
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
heap[index] = left;
heap[leftIndex] = node;
index = leftIndex;
}
} else if (right !== undefined && compare(right, node) < 0) {
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
return;
}
}
}
function compare(a, b) {
const diff = a.sortIndex - b.sortIndex;
return diff !== 0 ? diff : a.id - b.id;
}
const { push, pop, peek } = require('./SchedulerMinHeap');
let heap = [];
push(heap, { sortIndex: 1 });
push(heap, { sortIndex: 2 });
push(heap, { sortIndex: 3 });
console.log(peek(heap));
push(heap, { sortIndex: 4 });
push(heap, { sortIndex: 5 });
push(heap, { sortIndex: 6 });
push(heap, { sortIndex: 7 });
console.log(peek(heap));
pop(heap);
console.log(peek(heap));
ReactFiberLane.js
const NoLanes = 0b00;
const NoLane = 0b00;
const SyncLane = 0b01;
const SyncBatchedLane = 0b10;
/**
* 判断subset是不是set的子集
* @param {*} set
* @param {*} subset
* @returns
*/
function isSubsetOfLanes(set, subset) {
return (set & subset) === subset;
}
/**
* 合并两个车道
* @param {*} a
* @param {*} b
* @returns
*/
function mergeLanes(a, b) {
return a | b;
}
module.exports = {
NoLane,
NoLanes,
SyncLane,
SyncBatchedLane,
isSubsetOfLanes,
mergeLanes
}
ReactUpdateQueue.js
const { NoLane, NoLanes, isSubsetOfLanes, mergeLanes } = require('./ReactFiberLane') ;
function initializeUpdateQueue(fiber) {
const queue = {
baseState: fiber.memoizedState,//本次更新前该Fiber节点的state,Update基于该state计算更新后的state
firstBaseUpdate: null,//本次更新前该Fiber节点已保存的Update链表头
lastBaseUpdate: null,//本次更新前该Fiber节点已保存的Update链表尾
shared: {
//触发更新时,产生的Update会保存在shared.pending中形成单向环状链表
//当由Update计算state时这个环会被剪开并连接在lastBaseUpdate后面
pending: null
}
}
fiber.updateQueue = queue;
}
function enqueueUpdate(fiber, update) {
const updateQueue = fiber.updateQueue;
if (updateQueue === null) {
return;
}
const sharedQueue = updateQueue.shared;
const pending = sharedQueue.pending;
if (pending === null) {
update.next = update;
} else {
update.next = pending.next;
pending.next = update;
}
sharedQueue.pending = update;
}
/**
* 处理更新队列
* @param {*} fiber
* @param {*} renderLanes
*/
function processUpdateQueue(fiber, renderLanes) {
//获取此fiber上的更新队列
const queue = fiber.updateQueue;
//获取第一个更新
let firstBaseUpdate = queue.firstBaseUpdate;
let lastBaseUpdate = queue.lastBaseUpdate;
//判断一下是否在等待生效的的更新,如果有,变成base队列
let pendingQueue = queue.shared.pending;
if (pendingQueue !== null) {
//等待生效的队列是循环队列
queue.shared.pending = null;
//最后一个等待的更新 update4
const lastPendingUpdate = pendingQueue;
//第一个等待的更新 update1
const firstPendingUpdate = lastPendingUpdate.next;
//把环剪断,最后一个不再指向第一个
lastPendingUpdate.next = null;
//把等待生效的队列添加到base队列中
//如果base队列为空
if (lastBaseUpdate === null) {
firstBaseUpdate = firstPendingUpdate;
} else {//否则就把当前的更新队列添加到base队列的尾部
lastBaseUpdate.next = firstPendingUpdate;
}
//尾部也接上
lastBaseUpdate = lastPendingUpdate;
}
//开始计算新的状态
if (firstBaseUpdate !== null) {
//先获取老的值{number:0}
let newState = queue.baseState;
let newLanes = NoLanes;
let newBaseState = null;//新的基础状态
let newFirstBaseUpdate = null;//第一个跳过的更新
let newLastBaseUpdate = null;//新的最后一个基本更新
let update = firstBaseUpdate;//指向第一个更新
do {
//获取更新车道
const updateLane = update.lane;
//如果优先级不够,跳过这个更新,如果这是第一个跳过的更新,上一个状态和更新成为newBaseState和newFirstBaseUpdate
if (!isSubsetOfLanes(renderLanes, updateLane)) {
const clone = {
lane: updateLane,
payload: update.payload
};
if (newLastBaseUpdate === null) {
newFirstBaseUpdate = newLastBaseUpdate = clone;// first=last=update1
newBaseState = newState;//0
} else {
newLastBaseUpdate = newLastBaseUpdate.next = clone;
}
//更新队列中的剩下的优先级
newLanes = mergeLanes(newLanes, updateLane);
} else {
//如果有足够的优先级 如果有曾经跳过的更新,仍然追加在后面
if (newLastBaseUpdate !== null) {
const clone = {
//NoLane是所有的优先级的子集,永远不会被跳过
lane: NoLane,
payload: update.payload
};
newLastBaseUpdate = newLastBaseUpdate.next = clone;
}
newState = getStateFromUpdate(update, newState);
}
update = update.next;
if (!update) {
break;
}
} while (true);
if (!newLastBaseUpdate) {
newBaseState = newState;
}
queue.baseState = newBaseState;
queue.firstBaseUpdate = newFirstBaseUpdate;
queue.lastBaseUpdate = newLastBaseUpdate;
fiber.lanes = newLanes;
fiber.memoizedState = newState;
}
}
function getStateFromUpdate(update, prevState) {
const payload = update.payload;
let partialState = payload(prevState);
return Object.assign({}, prevState, partialState);
}
module.exports = {
initializeUpdateQueue,
enqueueUpdate,
processUpdateQueue
}
use.js
Depth First Search
function dfs(node) {
console.log(node.name);
node.children&&node.children.forEach(child => {
dfs(child);
});
}
let root = {
name: 'A',
children: [
{
name: 'B',
children: [
{ name: 'B1' },
{ name: 'B2' }
]
},
{
name: 'C',
children: [
{ name: 'C1' },
{ name: 'C2' }
]
}
]
}
dfs(root);
k
的所有顶点,然后再去搜索距离为k+l
的其他顶点function bfs(node) {
const stack = [];
stack.push(node);
let current;
while (current = stack.shift()) {
console.log(current.name);
current.children && current.children.forEach(child => {
stack.push(child);
});
}
}
let root = {
name: 'A',
children: [
{
name: 'B',
children: [
{ name: 'B1' },
{ name: 'B2' }
]
},
{
name: 'C',
children: [
{ name: 'C1' },
{ name: 'C2' }
]
}
]
}
bfs(root);
class Stack {
constructor() {
this.data = [];
this.top = 0;
}
push(node) {
this.data[this.top++] = node;
}
pop() {
return this.data[--this.top];
}
peek() {
return this.data[this.top - 1];
}
size() {
return this.top;
}
clear() {
this.top = 0;
}
}
const stack = new Stack();
stack.push('1');
stack.push('2');
stack.push('3');
console.log('stack.size()', stack.size());
console.log('stack.peek', stack.peek());
console.log('stack.pop()', stack.pop());
console.log('stack.peek()', stack.peek());
stack.push('4');
console.log('stack.peek', stack.peek());
stack.clear();
console.log('stack.size', stack.size());
stack.push('5');
console.log('stack.peek', stack.peek());
import React from "react";
const NumberContext = React.createContext(0);
export default function App() {
return (
<NumberContext.Provider value={'A'}>
<NumberContext.Consumer>
{(v1) => (
<NumberContext.Provider value={'B'}>
<NumberContext.Consumer>
{(v2) => (
<NumberContext.Provider value={'C'}>
<NumberContext.Consumer>
{(v3) => (
<div>
{v1} {v2} {v3}
</div>
)}
</NumberContext.Consumer>
</NumberContext.Provider>
)}
</NumberContext.Consumer>
</NumberContext.Provider>
)}
</NumberContext.Consumer>
</NumberContext.Provider>
);
}
src\react\packages\react-reconciler\src\ReactFiberStack.js
const valueStack = [];
let index = -1;
function createCursor(defaultValue) {
return {current: defaultValue};
}
function isEmpty() {
return index === -1;
}
function pop(cursor) {
if (index < 0) {
return;
}
cursor.current = valueStack[index];
valueStack[index] = null;
index--;
}
function push(cursor, value) {
index++;
valueStack[index] = cursor.current;
cursor.current = value;
}
module.exports = {
createCursor, isEmpty, pop, push
};
src\react\packages\react-reconciler\src\ReactFiberNewContext.js
function pushProvider(providerFiber, nextValue) {
const context = providerFiber.type._context;
push(valueCursor, context._currentValue, providerFiber);
context._currentValue = nextValue;
}
function popProvider(providerFiber) {
const currentValue = valueCursor.current;
pop(valueCursor, providerFiber);
const context = providerFiber.type._context;
context._currentValue = currentValue;
}
module.exports = {
pushProvider, popProvider
};
const { createCursor, pop, push } = require('./ReactFiberStack.js');
const { pushProvider, popProvider } = require('./ReactFiberNewContext.js');
let valueCursor = createCursor();
let providerFiber = { type: { _context: {} } };
pushProvider(providerFiber, 'A');
console.log(providerFiber.type._context._currentValue);
pushProvider(providerFiber, 'B');
console.log(providerFiber.type._context._currentValue);
pushProvider(providerFiber, 'C');
console.log(providerFiber.type._context._currentValue);
popProvider(providerFiber);
console.log(providerFiber.type._context._currentValue);
popProvider(providerFiber);
console.log(providerFiber.type._context._currentValue);
popProvider(providerFiber);
+ 00000001 # +1
- 00000001 # -1
10000000
的意思是-0,这个没有意义,所有这个数字被用来表示-1280 0000001 # +1
1 0000001 # -1
0 0000001 # +1
1 1111110 # -1
0 0000001 # +1
1 1111111 # -1
0b00000011
3
~0b00000011 => 0b11111100
-4
(~0b00000011).toString();
'-4'
(~0b00000011).toString(2);
'-100'
求补码的真值
1 表示负号
剩下的 1111100 开始转换
1111100 减1
1111011 取反
0000100 4
/**
* 分离出所有比特位中最右边的1
* 分离出最高优先级的车道
* @param {*} lanes 车道
* @returns 车道
*/
function getHighestPriorityLane(lanes) {
return lanes & -lanes;
}
lanes=0b00001100=12
-lanes=-12
1
0001100
1110011
1110100
11110100
00001100
(0b00000010<<1).toString(2)
(-0b111>>1).toString(2) "-100"
-0b111 -7
100000111 原码
111111000 反码
111111001 补码
111111100
1
111111100
111111011
000000100
1000000100
-100
-4
(0b111>>>1).toString(2)
>>> "11"
(-0b111>>>1).toString(2)
>>> "1111111111111111111111111111100"
00000000000000000000000000000111
11111111111111111111111111111000
11111111111111111111111111111001
01111111111111111111111111111100
2147483644