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

这个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位）

然后我们得到最终的二进制数：

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