关于javascript:前端大数的运算及相关知识总结

背景

前段时间我在公司的我的项目中负责的是权限治理这一块的需要。需要的大略内容就是零碎的管理员能够在用户治理界面对用户和用户表演的角色进行增删改查的操作，而后当用户进入主利用时，前端会申请到一个示意用户权限的数组usr_permission，前端通过usr_permission来判断用户是否领有某项权限。

这个usr_permission是一个长度为16的大数字符串数组，如下所示：

const usr_permission = [
  "17310727576501632001",
    "1081919648897631175",
    "4607248419625398332",
    "18158795172266376960",
    "18428747250223005711",
    "17294384420617192448",
    "216384094707056832",
    "13902625308286185532",
    "275821367043",
    "0",
    "0",
    "0",
    "0",
    "0",
    "0",
    "0",
]

数组中的每一个元素能够转成64位的二进制数，二进制数中的每一位通过0和1示意一种权限，这样每一个元素能够示意64种权限，整个usr_permission就能够示意16*64=1024种权限。后端之所以要对usr_permission进行压缩，是因为后端采纳的是微服务架构，各个模块在通信的过程中通过在申请头中退出usr_permission来做权限的认证。

数组usr_permission的第0个元素示意第[0, 63]号的权限，第1个元素示意第[64, 127]号的权限，以此类推。比方当初咱们要查找第220号权限：

const permission = 220 // 查看销售出库
const usr_permission = [
  "17310727576501632001",
    "1081919648897631175",
    "4607248419625398332",
    "18158795172266376960",
    "18428747250223005711",
    "17294384420617192448",
    "216384094707056832",
    "13902625308286185532",
    "275821367043",
    "0",
    "0",
    "0",
    "0",
    "0",
    "0",
    "0",
]

// "18158795172266376960" 示意第193号~第256号权限
// 1111 1100 0000 0000 1111 1111 1111 1111 1111 0000 0000 0011 1111 1111 0000 0000
// 220 % 64 = 28
// 0000 0000 0000 0000 0000 0000 0000 1111 1100 0000 0000 1111 1111 1111 1111 1111
// 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001
// -------------------------------------------------------------------------------
// 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001

从usr_permission中咱们得悉第220号权限由第3个元素”18158795172266376960″示意。
咱们将”18158795172266376960″转成二进制失去1111 1100 0000 0000 1111 1111 1111 1111 1111 0000 0000 0011 1111 1111 0000 0000。
将220除以64失去余数28，也就是说二进制数1111 1100 0000 0000 1111 1111 1111 1111 1111 0000 0000 0011 1111 1111 0000 0000从右数的第28位示意第220号权限。
咱们能够将二进制数1111 1100 0000 0000 1111 1111 1111 1111 1111 0000 0000 0011 1111 1111 0000 0000右移28位，将示意第220号权限的位数推到最低位。
而后将二进制数与1进行按位与操作，如果以后用户领有第220号权限，则最初失去的后果为1，反之为0。

以上就是前端查找权限的大抵过程，那么这个代码要怎么写呢？在编写代码之前，咱们先来温习一下JavaScript大数相干的常识，理解编写代码的过程中会遇到什么问题。

IEEE 754规范

在计算机组成原理这门课里咱们学过，在以IEEE 754为规范的浮点运算中，有两种浮点数值示意形式，一种是单精度（32位），还有一种是双精度（64位）。

在IEEE 754规范中，一个数字被示意成 +1.0001x2^3 这种模式。比如说在单精度（32位）表示法中，有1位用来示意数字的正负（符号位），8位用来示意2的幂次方（指数偏移值E，须要减去一个固定的数字失去指数e），23位示意1前面的小数位（尾数）。

比方0 1000 0010 0001 0000 0000 0000 0000 000，第1位0示意它是负数，第[2, 9]位1000 0010转换成十进制就是130，咱们须要减去一个常数127失去3，也就是这个数字须要乘以2的三次方，第[10, 32]位则示意1.0001 0000 0000 0000 0000 000，那么这个数字示意的就是二级制中的+1.0001*2^3，转换成十进制也就是8.5。

同理，双精度（64位）也是一样的表现形式，只是在64位中有11位用来示意2的幂次方，52位用来示意小数位。

JavaScript 就是采纳IEEE754 规范定义的64 位浮点格局示意数字。在64位浮点格局中，有52位能够示意小数点前面的数字，加上小数点后面的1，就有53位能够用来示意数字，也就是说64位浮点能够示意的最大的数字是2^53-1，超过2^53-1的数字就会产生精度失落。因为2^53用64位浮点格局示意就变成了这样：

符号位：0 指数：53 尾数：1.000000…000 （小数点后一共52个0）

小数点前面的第53个0曾经被抛弃了，那么2^53+1的64位浮点格局就会变得和2^53一样。一个浮点格局能够示意多个数字，阐明这个数字是不平安的。所以在JavaScript中，最大的平安数是2^53-1，这样就保障了一个浮点格局对应一个数字。

0.1 + 0.2 !== 0.3

有一道很常见的前端面试题，就是问你为什么JavaScript中0.1+0.2为什么不等于0.3？0.1转换成二进制是0.0 0011 0011 0011 0011 0011 0011 … （0011循环），0.2转换成二进制是0.0011 0011 0011 0011 0011 0011 0011 … （0011循环），用64位浮点格局示意如下：

// 0.1
e = -4;
m = 1.1001100110011001100110011001100110011001100110011010 (52位)

// 0.2
e = -3;
m = 1.1001100110011001100110011001100110011001100110011010 (52位)

而后把它们相加：

e = -4; m = 1.1001100110011001100110011001100110011001100110011010 (52位)
+
e = -3; m = 1.1001100110011001100110011001100110011001100110011010 (52位)

// 0.1和0.2指数不统一，须要进行对阶操作
// 对阶操作，会产生精度失落
// 之所以选0.1进行对阶操作是因为右移带来的精度失落远远小于左移带来的溢出
e = -3; m = 0.1100110011001100110011001100110011001100110011001101 (52位)
+
e = -3; m = 1.1001100110011001100110011001100110011001100110011010 (52位)


e = -3; m = 10.0110011001100110011001100110011001100110011001100111 (52位)

// 产生精度失落
e = -2; m = 1.00110011001100110011001100110011001100110011001100111 (53位)

咱们看到曾经溢出来了（超过了52位），那么这个时候咱们就要做四舍五入了，那怎么舍入能力与原来的数最靠近呢？比方1.101要保留2位小数，那么后果有可能是 1.10 和 1.11 ，这个时候两个都是一样近，咱们取哪一个呢？规定是保留偶数的那一个，在这里就是保留 1.10。

回到咱们之前的就是取m=1.0011001100110011001100110011001100110011001100110100 （52位）

而后咱们失去最终的二进制数：

1.0011001100110011001100110011001100110011001100110100 * 2 ^ -2

=0.010011001100110011001100110011001100110011001100110100

转换成十进制就是0.30000000000000004，所以，所以0.1 + 0.2 的最终后果是0.30000000000000004。

BigInt

通过后面的解说，咱们清晰地意识到在以前，JavaScript是没有方法对大于2^53-1的数字进行解决的。不过起初，JavaScript提供了内置对象BigInt来解决大数。BigInt 能够示意任意大的整数。能够用在一个整数字面量前面加 n 的形式定义一个 BigInt ，如：10n，或者调用函数BigInt()。

const theBiggestInt = 9007199254740991n;

const alsoHuge = BigInt(9007199254740991);
// ↪ 9007199254740991n

const hugeString = BigInt("9007199254740991");
// ↪ 9007199254740991n

typeof 1n === 'bigint'; // true
typeof BigInt('1') === 'bigint'; // true

0n === 0 // ↪ false

0n == 0 // ↪ true

用BigInt实现的权限查找代码如下：

hasPermission(permission: Permission) {
    const usr_permissions = this.userInfo.usr_permissions
    const arr_index = Math.floor(permission / 64)
    const bit_index = permission % 64
    if (usr_permissions && usr_permissions.length > arr_index) {
      if ((BigInt(usr_permissions[arr_index]) >> BigInt(bit_index)) & 1n) {
        return true
      }
    }
    return false
}

兼容剖析

然而BigInt存在兼容性问题：

依据我司用户应用浏览器版本数据的剖析，失去如下饼状图：

不兼容BigInt浏览器的比例占到12.4%

解决兼容性的问题，一种形式是如果心愿在我的项目中持续应用BigInt，那么须要Babel的一些插件进行转换。这些插件须要调用一些办法去检测运算符什么时候被用于BigInt，这将导致不可承受的性能损失，而且在很多状况下是行不通的。另外一种办法就是找一些封装大数运算办法的第三方库，应用它们的语法做大数运算。

用第三方库实现

很多第三方库能够用来做大数运算，大体的思路就是定义一个数据结构来寄存大数的正负及数值，别离算出每一位的后果再存储到数据结构中。

jsbn 解决方案

// yarn add jsbn @types/jsbn

import { BigInteger } from 'jsbn'

hasPermission(permission: Permission) {
    const usr_permissions = this.userInfo.usr_permissions
    const arr_index = Math.floor(permission / 64)
    const bit_index = permission % 64
    if (usr_permissions && usr_permissions.length > arr_index) {
      if (
        new BigInteger(usr_permissions[arr_index])
          .shiftRight(bit_index)
          .and(new BigInteger('1'))
          .toString() !== '0'
      ) {
        return true
      }
    }
    return false
  }

jsbi 解决方案

// yarn add jsbi

import JSBI from 'jsbi'

hasPermission(permission: Permission) {
    // 开发环境不受权限限度
    if (__DEVELOPMENT__) {
      return true
    }

    const usr_permissions = this.userInfo.usr_permissions
    const arr_index = Math.floor(permission / 64)
    const bit_index = permission % 64
    if (usr_permissions && usr_permissions.length > arr_index) {
      const a = JSBI.BigInt(usr_permissions[arr_index])
      const b = JSBI.BigInt(bit_index)
      const c = JSBI.signedRightShift(a, b)
      const d = JSBI.BigInt(1)
      const e = JSBI.bitwiseAnd(c, d)
      if (e.toString() !== '0') {
        return true
      }
    }
    return false
  }

权限查找新思路

起初，一位共事提到了一种新的权限查找的解决方案：前端获取到数组usr_permission当前，将usr_permission的所有元素转成二进制，并进行字符串拼接，失去一个示意用户所有权限的字符串permissions。当须要查找权限时，查找permissions对应的位数即可。这样相当于在用户进入零碎时就将所有的权限都算好，而不是用一次算一次。

在中学时，咱们学到的将十进制转成二进制的办法是辗转相除法，这里有一种新思路：

比方咱们要用5个二进制位示意11这个数
咱们须要先定义一个长度为5，由2的倍数组成的数组[16, 8, 4, 2, 1]，而后将11与数组中的元素挨个比拟
11 < 16，所以失去[0, x, x, x, x]
11 >= 8，所以失去[0, 1, x, x, x]，11 – 8 = 3
3 < 4，所以失去[0, 1, 0, x, x]
3 >= 2，所以失去[0, 1, 0, 1, x]，3 – 2 = 1
1>= 1，所以失去[0, 1, 0, 1, 1]，1 – 1 = 0，完结
所以用5位二进制数示意11的后果就是01011

依据下面的思路能够失去的代码如下，这里用big.js这个包去实现：

    import Big from 'big.js'    
    import _ from 'lodash'

    permissions = '' // 最初生成的权限字符串

    // 生成长度为64，由2的倍数组成的数组
    generateBinaryArray(bits: number) {
      const arr: any[] = []
      _.each(_.range(bits), (index) => {
        arr.unshift(Big(2).pow(index))
      })
      return arr
    }  

    // 将usr_permission中单个元素转成二进制
    translatePermission(binaryArray: any[], permission: string) {
    let bigPermission = Big(permission)
    const permissionBinaryArray: number[] = []
    _.each(binaryArray, (v, i) => {
      if (bigPermission.gte(binaryArray[i])) {
        bigPermission = bigPermission.minus(binaryArray[i])
        permissionBinaryArray.unshift(1)
      } else {
        permissionBinaryArray.unshift(0)
      }
    })
    return permissionBinaryArray.join('')
  }

    // 将usr_permission中所有元素的二进制模式进行拼接
  generatePermissionString() {
    const usr_permissions = this.userInfo.usr_permissions
    let str = ''
    const binaryArray = this.generateBinaryArray(64)
    _.each(usr_permissions, (permission, index) => {
      str = `${str}${this.translatePermission(binaryArray, permission)}`
    })
    this.permissions = str
  }

    // 判断时候领有某项权限
  hasPermission(permission: Permission) {
    if (!this.permissions) {
      return false
    }
    return this.permissions[permission] === '1'
  }

关于javascript:前端大数的运算及相关知识总结

背景

IEEE 754规范

0.1 + 0.2 !== 0.3

BigInt

兼容剖析

用第三方库实现

jsbn 解决方案

jsbi 解决方案

权限查找新思路

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于javascript:前端大数的运算及相关知识总结

背景

IEEE 754规范

0.1 + 0.2 !== 0.3

BigInt

兼容剖析

用第三方库实现

jsbn 解决方案

jsbi 解决方案

权限查找新思路

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复