前端大數的運算及相關知識總結

前段時間我在公司的項目中負責的是權限管理這一塊的需求。需求的大概内容就是系統的管理者可以在使用者管理界面對使用者和使用者扮演的角色進行增删改查的操作，然後當使用者進入主應用時，前端會請求到一個表示使用者權限的數組usr_permission，前端通過usr_permission來判斷使用者是否擁有某項權限。

這個usr_permission是一個長度為16的大數字元串數組，如下所示：

數組中的每一個元素可以轉成64位的二進制數，二進制數中的每一位通過0和1表示一種權限，這樣每一個元素可以表示64種權限，整個usr_permission就可以表示16*64=1024種權限。後端之是以要對usr_permission進行壓縮，是因為後端采用的是微服務架構，各個子產品在通信的過程中通過在請求頭中加入usr_permission來做權限的認證。

數組usr_permission的第0個元素表示第[0, 63]号的權限，第1個元素表示第[64, 127]号的權限，以此類推。比如現在我們要查找第220号權限：

從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為标準的浮點運算中，有兩種浮點數值表示方式，一種是單精度（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，這樣就保證了一個浮點格式對應一個數字。

有一道很常見的前端面試題，就是問你為什麼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位浮點格式表示如下：

然後把它們相加：

我們看到已經溢出來了（超過了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。

通過前面的講解，我們清晰地認識到在以前，JavaScript是沒有辦法對大于2^53-1的數字進行處理的。不過後來，JavaScript提供了内置對象BigInt來處理大數。BigInt 可以表示任意大的整數。可以用在一個整數字面量後面加 n 的方式定義一個 BigInt ，如：10n，或者調用函數BigInt()。

用BigInt實作的權限查找代碼如下：

但是BigInt存在相容性問題：

根據我司使用者使用浏覽器版本資料的分析，得到如下餅狀圖：

不相容BigInt浏覽器的比例占到12.4%

解決相容性的問題，一種方式是如果希望在項目中繼續使用BigInt，那麼需要Babel的一些插件進行轉換。這些插件需要調用一些方法去檢測運算符什麼時候被用于BigInt，這将導緻不可接受的性能損失，而且在很多情況下是行不通的。另外一種方法就是找一些封裝大數運算方法的第三方庫，使用它們的文法做大數運算。

很多第三方庫可以用來做大數運算，大體的思路就是定義一個資料結構來存放大數的正負及數值，分别算出每一位的結果再存儲到資料結構中。

後來，一位同僚提到了一種新的權限查找的解決方案：前端擷取到數組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這個包去實作：