<

1.位运算 #

1.1 比特 #

bit

0b1000=2*2*2=Math.pow(2,3)=8=0~7

1.2 数值数据 #

1.2.1 无符号数据的表示 #

1.2.2 有符号数据的表示 #

1.2.2.1 原码 #

1.2.2.2 反码 #

1.2.2.3 补码 #

1.3 位运算 #

运算 使用 说明
按位与(&) 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));

1.4 使用 # 

//定义常量
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);

1.5 ES5规范 #

1.6 Hydration #




1.7 React中的应用场景 # 

//一共有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

2. 最小堆 #

2.1 二叉树 #

2.2 满二叉树 #

2.3 完全二叉树 #

2.4 最小堆 #

2.5 SchedulerMinHeap.js #

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));

3. 链表 #

3.1 链表分类 #

3.1.1 单向链表 #

3.1.2 双向链表 #

3.1.3 循环链表 #

3.1.4 示例 #

3.1.4.1 ReactFiberLane.js #

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
}
3.1.4.2 ReactUpdateQueue.js #

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
}
3.1.4.3 use.js #

use.js

4. 树的遍历 #

4.1 深度优先(DFS) # 

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);

4.2 广度优先(BFS) # 

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);

5. 栈 #

5.1 栈代码 # 

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());

5.2 应用场景 #

5.2.1 App.js # 

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>
    );
}

5.2.2 ReactFiberStack.js #

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
};

5.2.3 ReactFiberNewContext.js #

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
};

5.2.4 use.js # 

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);

6.二进制 #

6.1 真值 # 

+ 00000001 # +1
- 00000001 # -1

6.2 原码 # 

0 0000001 # +1
1 0000001 # -1

6.3 反码 # 

0 0000001 # +1
1 1111110 # -1

6.4 补码 # 

0 0000001 # +1
1 1111111 # -1

6.5 二进制数整数 #

6.6 ~非 # 

0b00000011
3
~0b00000011 =>  0b11111100
-4
(~0b00000011).toString();
'-4'
(~0b00000011).toString(2);
'-100'

求补码的真值
1 表示负号
剩下的 1111100 开始转换
1111100 减1
1111011 取反
0000100 4

6.7 getHighestPriorityLane # 

/**
 * 分离出所有比特位中最右边的1
 * 分离出最高优先级的车道
 * @param {*} lanes 车道
 * @returns 车道
 */
function getHighestPriorityLane(lanes) {
    return lanes & -lanes;
}

lanes=0b00001100=12
-lanes=-12
1
0001100
1110011
1110100
11110100
00001100

6.8 左移 # 

(0b00000010<<1).toString(2)

6.9 >> 有符号右移 # 

(-0b111>>1).toString(2) "-100"
-0b111 -7
100000111 原码
111111000 反码
111111001 补码
111111100

1
111111100
111111011
000000100
1000000100
-100
-4

6.10 >>>无符号右移 # 

(0b111>>>1).toString(2)
>>> "11"

(-0b111>>>1).toString(2)
>>> "1111111111111111111111111111100"

00000000000000000000000000000111
11111111111111111111111111111000
11111111111111111111111111111001
01111111111111111111111111111100
2147483644