网络日志

二进制之简介和应用

博主博客首发

前言

计算机内部是一个由0和1组成的二进制世界,我们所有的操作最终都会转换成二进制进行运算和存储,这是因为在电子计算机出现时,是使用电子管来进行状态管理的,而它也就只有“”和“”(通、断电)这两种最基本的状态,这也就决定了计算机用二进制来表述数字和数据是最容易实现的,而它的通用性在科技如此发达的今天依然无法被替代。 二进制数据是用01两个数码来表示的数。它的基数为2,进位规则是“逢二进一”,借位规则是“借一当二

有趣的特征

  • 如果一个二进制第零位(最右侧)的值为1,则这个数一定是个奇数;而如果该位是0,那么这个数就是偶数
  • 2ⁿ-1转换成二进制是n个1;例:2³ = 7(十进制) = 111(二进制)
  • 将一个二进制数的所有位左移1位的结果是将该数乘以二;例:7<<1等于14;7的二进制为111,移位后为1110=14

    进制间的转换

    正数间的转换

  • 十进制转二进制:除2取余,逆序排列
57 % 2 = 28 余 1
28 % 2 = 14 余 0
14 % 2 = 7  余 0
 7 % 2 = 3  余 1
 3 % 2 = 1  余 1
 1 % 2 = 0  余 1

结果为(倒取):111001

  • 二进制转十进制:取不为0的位置序号作为2的次方进行计算,并将结果进行相加
// 111001
Math.pow(2, 5) + Math.pow(2, 4) + Math.pow(2, 3) + Math.pow(2, 0) === 57

小数间的转换

  • 十进制转二进制:乘2取整,正序排列

    0.375 * 2 = 0.750 取整 0
    0.750 * 2 = 1.500 取整 1
    0.500 * 2 = 1.000 取整 1

    结果为:0.011

  • 二进制转十进制:取小数点后不为0的位置序号作为2的负次方进行计算,并将结果进行相加

    // 0.011
    Math.pow(2, -2) + Math.pow(2, -3) === 0.375

    负数间的转换

    说到二进制负数首先要介绍三个名词:原码反码补码,因为在计算机内部,负数是以补码的形式存在的

    原码:正数的原码为其绝对值转二进制;负数的原码为其绝对值转二进制然后最高位补1反码:正数的反码和原码一至;负数的反码为其原码除符号位外各位取反补码:正数的补码和原码一至;负数的反码为其原码除符号位外各位取反,然后再加1
  • 十进制转二进制(八进制为例):

    • -57的绝对值转二进制:111001
    • 最高位补1:10111001
    • 处符号位取反:11000110
    • 最高位加1:11000111结果为:11000111
  • 二进制转十进制则返回来算就可以了

    问题分析

    有了上面的知识,那么0.1+0.2 !== 0.3就有了一个最简单、容易理解的解释了:转二进制算不开,会出现无限循环部分,所以就会精度丢失,具体可以参考 为什么0.1+0.2不等于0.3

    位运算介绍

    逻辑与:AND,操作符:&

两个对应的二进制位都为1时,结果为1;例:

    1101   ->  13
AND 1001   ->  9
------------------
    1001   ->  9

判断一个数的奇偶就可以应用这个特性:

18 & 1 === 1 // false,
19 & 1 === 1 // true,

原理就是因为所有的奇数转成二进制后最后一位为1,而偶数最后为0,当他们和1做按位与操作时,得到的结果只有”1“(奇数)和”0“(偶数)两种情况

逻辑或:OR,操作符:|

两个对应的二进制位有一个为1时,结果就为1;例:

   1101   ->  13
OR 1001   ->  9
------------------
   1101   ->  13

取整是其中一种应用:

function toInt(num) {
  return num | 0
}
console.log(toInt(3.2))     // 3
console.log(toInt(2.12345)) // 2

逻辑异或:XOR,操作符:^

两个对应的二进制位相同为0,相异为1例:

    1101   ->  13
XOR 1001   ->  9
--------------------
    0100   ->  4

可以应用此特性实现不借助新的变量来交换两个变量的值

var a = 10, b = 20
a ^= b
b ^= a
a ^= b
console.log(a,b) // 20,10
// 10 = 01010
// 20 = 10100
// a  = 11110   # a ^ b的结果,其中的1是 a 和 b 中不同的部分 
// b  = 01010   # b ^ c的结果,有没有发现和a是一样的
// a  = 10100   # a ^ d的结果,有没有发现是b是一样的

逻辑非:NOT,操作符:~

0变1,1变0;例(八位):

NOT     1001
-------------
    11110110

按位左移:SHL,操作符:<<

各二进位全部左移若干位,右侧丢弃,左侧补0例:

         57:111001
-------- 57 << 1 -------
运算结果:114:1110010

一个简单的乘法小技巧:

num << 1    // num * 2
num << 2    // num * 4
num << 3    // num * 8

按位右移:SHR,操作符:>>>>>

>>:有符号位位移;各二进位全部右移若干位,右侧丢弃,左侧补符号位 >>>:无符号位位移;各二进位全部右移若干位,右侧丢弃,左侧补0

         57:111001
-------- 57 >> 1 ---------
运算结果:28:11100

一个简单的整除小技巧:

num >> 1    // num / 2
num >> 2    // num / 4
num >> 3    // num / 8

位运算在VUE3.0中的应用

在vue3.0中,和vnode元素相关的判断和更新中就有大量关于位运算的操作

// packages/shared/src/shapeFlags.ts
export const enum ShapeFlags {
  ELEMENT = 1,  // 普通HTML:0000000001
  FUNCTIONAL_COMPONENT = 1 << 1, // 函数式组件:0000000010
  STATEFUL_COMPONENT = 1 << 2,  // 有状态组件:0000000100
  TEXT_CHILDREN = 1 << 3, // 子节点为纯文本:0000001000
  ARRAY_CHILDREN = 1 << 4, // 子节点为数组:0000010000
  SLOTS_CHILDREN = 1 << 5, // 子节点为插槽:0000100000
  TELEPORT = 1 << 6, //0001000000
  SUSPENSE = 1 << 7, //0010000000
  COMPONENT_SHOULD_KEEP_ALIVE = 1 << 8, // 未被 keep-alive的有状态组件:0100000000
  COMPONENT_KEPT_ALIVE = 1 << 9, //  keep-alive中有状态组件:1000000000
  COMPONENT = ShapeFlags.STATEFUL_COMPONENT | ShapeFlags.FUNCTIONAL_COMPONENT // 有状态和无状态组件的结合体:0000000110
}
// 用于标识节点更新类型: packages/shared/src/patchFlags.ts
// 还有:packages/shared/src/slotFlags.ts

createVNode创建节点时,会通过shapeFlag标记当前节点类型和其子节点类型

function createBaseVNode( type, children, patchFlag, shapeFlag) {
    const vnode = { type, children, patchFlag, shapeFlag }
    if (children) {
        // 通过位运算在shapeFlag中添加children的类型
        //1、  如果标签被标记为element,则二进制为:  0000000001
        //1.1、若childen被标记为纯文本,则二进制变为:0000001001
        //1.2、若childen若标记为数组,则二进制变为:  0000010001
        vnode.shapeFlag = vnode.shapeFlag | (isString(children) ? ShapeFlags.TEXT_CHILDREN : ShapeFlags.ARRAY_CHILDREN)
    }
    return vnode
}
function _createVNode(type, props, children){
    // 如果type是字符串,就将当前节点当做element节点
    const shapeFlag = isString(type) ? ShapeFlags.ELEMENT : ShapeFlags.FUNCTIONAL_COMPONENT // 简写,实际判断以原码为准
    return createBaseVNode(
        type,
        children,
        patchFlag,
        shapeFlag
    )
}

patch阶段,则就会对createVNode时创建的shapeFlag,进行逻辑与(&)运算来判断标签类型

const patch = (n1, n2) => {
    const { type, ref, shapeFlag } = n2
    switch (type) {
        // ...
        // 省略针对文本、注释、根节点等判断
        default:
            // 根据shapeFlag判断标签类型
            if (shapeFlag & ShapeFlags.ELEMENT) { // 打包后回变成shapeFlag & 1
                processElement() // 处理标签时还需要处理其内部子元素
            } else if (shapeFlag & ShapeFlags.COMPONENT) { // 打包后会变成shapeFlag & 6
                processComponent()
            } else if (shapeFlag & ShapeFlags.TELEPORT) { // 打包后会变成shapeFlag & 64
                ;(type as typeof TeleportImpl).process()
            } else if (__FEATURE_SUSPENSE__ && shapeFlag & ShapeFlags.SUSPENSE) { // 打包后会变成shapeFlag & 128
                ;(type as typeof SuspenseImpl).process()
            }
    }
}

processElement函数则会调用mountElement进行元素的初次渲染和内部子元素判断

const mountElement = (vnode) => {
    // ...略
    if (shapeFlag & ShapeFlags.TEXT_CHILDREN) { // 子元素是文字
        hostSetElementText(el, vnode.children as string)
    } else if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) { // 子元素是数组
        // mountChildren(vnode.children)
        // 调用patch对子元素进行重新判断
        for (let i = 0; i < vnode.children.length; i++) {
            const child = (children[i] = optimized? cloneIfMounted(children[i]): normalizeVNode(children[i]));
            patch()
        }
    }
}

根据上面的逻辑可以看到:如果shapeFlag为0000010001;其与ShapeFlags.ELEMENTShapeFlags.ARRAY_CHILDREN进行逻辑与运算,当结果都是非0的值,最后就会成功进入patch children阶段; 其实vue3.0在处理VNode这种最关键的性能损耗方面做了非常多的优化,二进制运算优化只是其中一种,但是在代码中熟练运用二进制运算,对运算复杂度、逻辑判断、运行性能和代码体积上都会有非常大的提升

通过位运算实现简单的权限控制判断

在程序中,熟练的使用二进制运算可以减少代码的逻辑判断、增强代码扩展性、易于存储及提升效率。而权限判断,算是比较常见的一种应用场景,无论是linux内部的部分权限控制还是大型的管理系统都有非常多的实践应用。 假设现在系统需要三种权限增加删除修改,则我们只需要用一个number类型的变量就可以控制所有权限类型,同时在将权限存储数据库时也只需要存储这一个变量即可

// 定义权限
const enum permissions {
  ADD = 1, // 1
  DELETE = 1 << 1, // 2
  UPDATE = 1 << 2 // 4
}

class userRole {
  private roles: number;
  constructor() {
    this.roles = 0
  }
  public addRole(role: number): void {
    this.roles |= role
    // 和上面等价
    // if (!this.hasRole(role)) {
    //   this.roles += role
    // }
  }
  public removeRole(role: number): void {
    this.roles &= (~role);
    // 和上面等价
    // if (this.hasRole(role)) {
    //   this.roles -= role 
    // }
  }
  // 有至少一个权限
  public hasRole(role: number | number[]): boolean {
    let roles:number[] = typeof role === 'number' ? [ role ] : role
    for (let i = 0; i < roles.length; i++) {
      if (!!(this.roles & roles[i])) {
        return true
      }
    }    
    return false
  }
  // 有所有权限
  public hasBothRole(role: number | number[]): boolean {
    let roles:number[] = typeof role === 'number' ? [ role ] : role
    for (let i = 0; i < roles.length; i++) {
      if (!(this.roles & roles[i])) {
        return false
      }
    }    
    return true
  }
  public resetRole(): void {
    this.roles = 0
  }
}

const myRole = new userRole()
console.log(myRole.hasRole(permissions.ADD)); // false

myRole.addRole(permissions.ADD)
myRole.addRole(permissions.DELETE)
console.log(myRole.hasRole([permissions.ADD, permissions.DELETE])); // true

myRole.removeRole(permissions.DELETE)
console.log(myRole.hasRole([permissions.ADD, permissions.DELETE])); // true
console.log(myRole.hasBothRole([permissions.ADD, permissions.DELETE])); // false

以上就是一个简单使用二进制进行权限判断的逻辑,如果尝试使用非二进制实现此函数会发现,二进制方案在权限判断时会少一些逻辑判断和代码,代码效率就更不用说了!