Shulou(Shulou.com)06/03 Report--

This article mainly explains "what is the operation of front-end large numbers and related knowledge". Interested friends might as well take a look at it. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn "what is the operation of front-end large numbers and related knowledge"?

Background

Some time ago, I was responsible for the requirements of rights management in the company's project.

This usr_permission is an array of large numeric strings of length 16, as follows:

Const usr_permission = [17310727576501632001 "," 1081919648897631175 "," 4607248419625398332 "," 18158795172266376960 "," 18428747250223005711 "," 17294384097056832 "," 13902625308286185532 "," 275821367043 "," 0 "," 0 "," 0 "," 0 "," 0 "," 0 "]

Each element in the array can be converted to a 64-bit binary number, and each bit in the binary number represents a permission through 0 and 1, so that each element can represent 64 permissions, and the entire usr_permission can represent 16 permissions 64 permissions 1024 permissions. The reason why the backend compresses the usr_permission is that the backend uses the micro-service architecture, and each module authenticates the permissions by adding usr_permission to the request header in the process of communication.

The 0th element of the array usr_permission represents the permissions of [0,63], the first element represents the permissions of [64,127], and so on. For example, now we need to find permission 220:

-/ / 0000 0000 0000 0001

We know from usr_permission that permission 220 is represented by the third element "18158795172266376960".

We convert "18158795172266376960" to binary to get 1111 1100 0000 0000 1111 1111 1111 0000 0000 0011 1111 0000 0000 0000.

Divide 220 by 64 to get the remainder 28, that is, the binary number 1111 1100 0000 0000 1111 1111 1111 0000 0000 0011 1111 1111 0000 0000 represents permission 220 from the 28th bit of the right.

We can move the binary number 1111 1100 0000 0000 1111 1111 1111 0000 0000 0011 1111 1111 0000 0000 to the right, pushing the number of digits indicating permission 220 to the lowest level.

Then bitwise and operate the binary number with 1, and if the current user has permission 220, the final result is 1, and vice versa.

The above is the general process of finding permissions at the front end, so how to write this code? Before writing code, let's review the knowledge about JavaScript large numbers to understand what problems you will encounter in the process of writing code.

IEEE 754 standard

In the course of computer composition principles, we learned that in floating-point operations based on IEEE 754, there are two ways to represent floating-point values, one is single-precision (32-bit), and the other is double-precision (64-bit).

In the IEEE 754 standard, a number is represented as + 1.0001x2 ^ 3. For example, in the single-precision (32-bit) representation, 1 bit is used to represent the positive and negative (symbol bits) of the number, 8 bits are used to represent the power of 2 (exponential offset value E, you need to subtract a fixed number to get the exponent e), and 23 bits represent the decimal places after 1 (Mantissa).

For example, 0 1000 0010 0001 0000 0000 0000, the first bit 0 indicates that it is a positive number, and the [2,9] bit 1000 0010 is converted to decimal system, and we need to subtract a constant 1000 to get 3, that is, this number needs to be multiplied by the third power of 2, and the [10,32] bit represents 0000 0000000000000, then this number represents + 1.0001 * 2 ^ 3 in the two-tier system.

Similarly, double precision (64 bits) is the same, except that 11 of the 64 bits are used to represent the power of 2, and 52 bits are used to represent decimal places.

JavaScript represents numbers in a 64-bit floating-point format defined by the IEEE754 standard. In 64-bit floating-point format, 52 digits can represent the number after the decimal point, and plus the 1 before the decimal point, there are 53 digits that can be used to represent numbers, that is, the maximum number that 64-bit floating point can represent is 2 ^ 53-1. A number that exceeds 2 ^ 53-1 will lose precision. Because 2 ^ 53 is represented in 64-bit floating-point format like this:

Symbol: 0 Index: 53 Mantissa: 1.000000.000 (52 zeros after the decimal point)

The 53rd 0 after the decimal point has been discarded, so the 64-bit floating-point format of 2 ^ 53 + 1 becomes the same as 2 ^ 53. A floating-point format can represent multiple numbers, indicating that the number is unsafe. So in JavaScript, the maximum safe number is 2 ^ 53-1, which ensures that a floating-point format corresponds to a number.

0.1 + 0.2! = 0.3

There is a very common front-end interview question, that is, why is 0.1% 0.2 not equal to 0.3 in JavaScript? 0.1 conversion to binary is 0011 0011 0011. (0011 loop), 0.2 conversion to binary is 0.0011 0011 0011 0011 001100110011. (0011 loop), expressed in 64-bit floating point format as follows:

/ / 0.1 e =-4; m = 1.100110011001100110011001100110011001100110011001100110011010 (52 bits) / / 0.2 e =-3; m = 1.100110011001100110011001100110011001100110011010 (52 bits)

And then add them up:

E =-4; m = 1.1001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001 M = 1.10011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100111100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001

We see that it has spilled over (more than 52 places), so at this time we have to do rounding, so how can rounding be closest to the original number? For example, if 1.101 wants to keep 2 decimal places, then the result may be 1.10 and 1.11, both of which are equally close at this time, which one should we choose? The rule is to keep the even number, which in this case is 1.10.

Before going back to us, it is to take masking 1.00110011001100110011001100110011001100110011001100110100 (52 bits).

Then we get the final binary number:

1.0011001100110011001100110011001100110011001100110011001100110100 * 2

= 0.010011001100110011001100110011001100110011001100110100

Converting to decimal is 0.300000000000004, so the end result of 0.1 + 0.2 is 0.300000000000004.

BigInt

Through the previous explanation, we clearly realized that in the past, JavaScript had no way to deal with numbers greater than 2 ^ 53-1. Later, however, JavaScript provided a built-in object, BigInt, to handle large numbers. BigInt can represent any large integer. You can define a BigInt by adding n after an integer number, such as: 10n, or call the function 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

The permission lookup code implemented with BigInt is as follows:

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} compatibility Analysis

However, there are compatibility issues with BigInt:

According to the analysis of the browser version data of our users, the following pie chart is obtained:

12.4% of them are not compatible with BigInt browsers.

One way to solve the compatibility problem is if you want to continue to use BigInt in your project, then you need some plug-ins for Babel to convert it. These plug-ins need to call methods to detect when operators are being used in BigInt, which results in unacceptable performance degradation and, in many cases, does not work. Another way is to find some third-party libraries that encapsulate large number operations and use their syntax to do large number operations.

Implemented with a third-party library

Many third-party libraries can be used to do large number operations, the general idea is to define a data structure to store the positive and negative and numerical values of large numbers, calculate the results of each bit and then store them in the data structure.

Jsbn solution / / 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 solution / / yarn add jsbi import JSBI from 'jsbi' hasPermission (permission: Permission) {/ / the development environment is not restricted by permissions 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} New ideas for permission search

Later, a colleague mentioned a new solution for permission lookup: after the front end gets the array usr_permission, it converts all the elements of usr_permission into binary and concatenates strings to get a string permissions that represents all the permissions of the user. When you need to find permissions, you can find the number of digits corresponding to permissions. This is equivalent to counting all permissions well when the user enters the system, rather than using them one at a time.

In high school, the way we learned to convert decimal to binary is division. Here's a new idea:

For example, we're going to use five binary bits to represent the number 11.

We need to define an array of length 5 and multiples of 2 [16, 8, 4, 2, 1], and then compare 11 with the elements in the array one by one.

eleven

= 8, so get [0,1, x, x], 11-8 = 3

three

= 2, so get [0,1,0,1, x], 3-2 = 1

1 > = 1, so get [0,1,0,1,1], 1-1 = 0, end

So the result of representing 11 with a 5-digit binary number is 01011.

The code that can be obtained according to the above idea is as follows, which is implemented with the package big.js:

Import Big from 'big.js' import _ from' lodash' permissions =''/ / the last generated permission string / / the generated length is 64 Array generateBinaryArray (bits: number) {const arr: any [] = [] _ .each (_ .range (bits), (index) = > {arr.unshift (Big (2) .pow (index)}) return arr} / / converts a single element in usr_permission to binary 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 ('')} / / concatenate the binary form of all elements in 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'} so far I believe that everyone on the "front-end large number operation and related knowledge have what" have a deeper understanding, might as well to the actual operation of it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.