Writing in the front
All the Buddha is updated, the Buddha is a bit long, long time no post, there are a lot of friend drop me, actually because of changing jobs and moving, rhythm and time are adjusted, and even then a short period of time a little anxiety, you know, is now gradually stable, you can get a higher frequency should be next, ollie to ~
May be some of you can immediately start to see or is the face of the article more inclined to some, to tell the truth, you may be able to deceive the interviewer, after all, but their own, should bear in mind the technology! Many people tend to ignore the foundation of a building, but it is the foundation that determines the height of the building
A few days ago a friend asked me a operation, actually was going to write article bit operations, but describing an operation is the premise of need you can clearly understand the number in the computer, digital and bit operation is different two points, so direct dubious bit operations may not be so good, just took out the article tinker hair once, Is also to fill a fill before writing half of the strike, then reissue a bit operation of the article
Numbers, very ordinary things, all languages have Numbers, most of the knowledge point of this article is not only suitable for JavaScript, other languages are similar, the surface figure there may be a very simple, actually from the computer to the language itself on digital processing is more complex, hope this paper can reflects the number of subtlety, so named The beauty of digital
binary
For the computer can only store binary, must be everyone familiar knowledge
We all know that the internal computer data storage and computing using binary, because a computer is made up of many transistors, and the transistor with just two states and can be expressed in binary 1 s and 0 s, and USES the binary can make internal computer algorithm is simple, high stability, but because we don’t usually use binary directly, So for those of you who have forgotten how to convert decimal to binary, here’s a quick review
Integer to binary
About decimal integer to binary, actually very simple, remember a secret, can be
In addition to2Mod, reverse orderCopy the codeThat is, divide the decimal number exactly by 2 to get the quotient and remainder, and then divide the quotient exactly by 2 to get the new quotient and remainder, and repeat until the quotient is equal to 0. The remainder obtained first as the high order of the binary number, and the remainder obtained later as the low order of the binary number, in order
For example, we convert decimal 55 to base 2
55 % 2 // 27 has a remainder of 1
27 % 2 // 13 leaves 1
13 % 2 // 6 leaves 1
6 % 2 // The remainder is 0
3 % 2 // 1 is left over 1
1 % 2 // The remainder of 0 is 1
Copy the codeMod inverse, the result of 55 to 2 decimal is 110111
A binary number is 1 bit, so if we need to get 8 bits of binary, we just add 0 before the conversion result
For example, if the 8-bit binary of decimal 55 is 00110111, then some people may also wonder what if it is 4 bits, 4 bits can not store such a large value of 55, overflow
Decimal to binary
For those of you who don’t know how to convert decimal to binary, there’s a formula, right
take2Round it up and put it in orderCopy the codeIn 2 decimal fraction, can get the product, the product of the integer part, and in 2 by the rest of the decimal part, and get a product, and then remove the integer part of the product, and so on, until all the integer part is zero, the product or the integer part is 1, 0 or 1 at this time is the last of the binary or to achieve the required accuracy, The extracted integer parts are then arranged in order, with the first integer as the highest significant bit of the binary decimal and the second integer as the lowest significant bit
For example, convert the decimal number 0.625 to binary
0.625 * 2 = 1.250 // Take the integer 1
0.25 * 2 = 0.50 // Take the integer 0
0.5 * 2 = 1 // Take the integer 1 and end
Copy the codeRounded order, then the binary of the decimal 0.625 is 0.101
If the decimal value is a decimal greater than 1, then the integer part and the decimal part can be concatenated by binary
For example, convert the decimal number 5.125 to binary
Let’s start with the binary of the integer 5
5 % 2 // 2 leaves 1
2 % 2 // The number of times 1 remains 0
1 % 2 // The remainder of 0 is 1
Copy the codeSo the binary of 5 is 101, and then the decimal part
0.125 * 2 = 0.250 // Take the integer 0
0.25 * 2 = 0.50 // Take the integer 0
0.5 * 2 = 1 // Take the integer 1 and end
Copy the codeThe binary of the decimal part 0.125 is 001, and the concatenation of the decimal number 5.125 is 101.001
There is also a case where, for example, the decimal number 0.1 is binary
0.1 * 2 = 0.2 // Take the integer 0
0.2 * 2 = 0.4 // Take the integer 0
0.4 * 2 = 0.8 // Take the integer 0
0.8 * 2 = 1.6 // Take the integer 1
0.6 * 2 = 1.2 // Take the integer 1 -> here we see the start of an infinite loop
0.2 * 2 = 0.4 // Take the integer 0
0.4 * 2 = 0.8 // Take the integer 0.Copy the codeSo its binary is 0.0001100…… This repeated cycle, which also leads to our problems in the language level, such as JS is criticized 0.1 + 0.2! = 0.3, we’ll talk about that later
Source, inverse, and complement
Again before the JS number problem, we also need to supplement to understand the concept of the original code, inverse code and complement, here not to say the conclusion, we step by step, finally summarize what is the original code, inverse code and complement
The origin of
The computer stores the most primitive numbers, those without positive and negative numbers, which we call unsigned numbers
If we store an unsigned number in memory with four bits, it looks like this
PS: Here also said is if, of course you also can use a 32 bit to understand, here only to explain the concept of the original code, radix-minus-one complement and complement, how many there is only one difference, that is the range of values can be stored in different sizes, can store the digits, the greater the can be stored, the greater the range of values that would say that behind all of this is not important, main is a 32-bit drawing too tired…
We might have noticed that there’s no way to express negative numbers
So, in order to express positive and negative, our ancestors invented the original code, which left the first place to store symbols. Positive numbers are represented by 0, and negative numbers are represented by 1
In case you are wondering why I only drew the number 7 in the table above, it also says that the example we use here is the 4-bit storage, only 4 bits, and one sign bit. The binary representation of decimal 7 is 0111. The number 8 binary is 01000, which is 5 bits, not 4 bits. Therefore, when only 4 bits are stored in the binary, the value of the source code is only -7 to +7
Source code this way is very good for people to understand, but the machine does not understand ah, the expression value is no problem, but how to add the plus and minus?
So if we wanted to use (+1) + (-1), which we know from elementary school is equal to 0, but in binary computing, 0001 + 1001 = 1010, let’s compare the original code table, which is -2
Obviously, that’s not the right way to calculate it, and we’ll see that the 0 in the source code is represented in two ways: +0 and -0, which is obviously not the right way to calculate it
In order to solve the problem that the sum of positive and negative is equal to 0, our ancestors invented inverse code on the basis of the original code
The inverse of the positive number is still the same as the original code, the expression of the inverse code is actually used to deal with negative numbers, that is, except the symbol bit is unchanged, the other positions are taken inverse storage, 0 is stored 1,1 is stored 0
So let’s see
As above, the value storage range of 4-bit inverse code is also -7 ~ +7
When the original code becomes the inverse code, we look at the previous (+1) and (-1) add, become 0001 + 1110 = 1111, add results compared to the anti-code table, 1111 is -0, perfect solution to the plus and minus is equal to 0
However, if you use inverse code to store numbers, you still have the problem of having two different binary representations of the same value (+0) and (-0)
Therefore, in order to solve this problem, our predecessors put forward the concept of complement code, which also deals with negative numbers. That is, a new code 1 is added on the basis of the original inverse code
As shown in the figure above, when dealing with the -0 in the inverse code, we add another 1 to 1111 and it becomes 10000. Since we are storing four bits, we throw away the left-most digit of the division bit, the one in the carry, and it becomes 0000, which is exactly the same as the positive 0 on the left
It perfectly solves the problem of both (+0) and (-0)
Since the complement of -0 is 0000, which is the same thing as +0, because it complements 1, we find that -0 is meaningless, so we get rid of the number -0
If we look at the complement of minus 7, that is, the binary expression of the inverse code after adding 1, 1001. In the form of 4-bit storage, we find that the complement table 1001 can be smaller by one bit, namely 1000, namely -8, as shown in the following figure
Thus, a -8 is added to the end of the complement, which is expressed in the range of -8 to +7 in the 4-bit memory
At the same time, when we use the complement, we can also solve the problem that the addition of positive and negative is equal to 0
Ex. :
We add (+4) and (-4), 0100 + 1100 =10000, carry, throw away the highest digit, which is 0000 (0).
Next we can comb and summarize what is the original code, inverse code, complement code
The original code
The original code is actually a sign bit added before the value (that is, the highest bit is the sign bit), the sign bit is 0 when the positive number
The sign bit for negative numbers is 1 (0 is represented in two ways: +0 and -0), and the remaining bits indicate the size of the number
Ex. :
This time we use 8-bit binary to represent a number, so the source code for positive 5 is 0000 0101, and the source code for negative 5 is 1000 0101, the only difference being the sign bits
Radix-minus-one complement
The inverse of a positive number is the same as its original code
The inverse of a negative number is the inverse of its source code except the sign bit
Ex. :
When 12 bits are used to represent a numeric value, the inverse of positive 5 is equal to the original code (0000 0000 0101), the symbol bit of negative 5 is 1, and the other inverse is 1111 1111 1010
complement
The complement of a positive number is the same as its source
The complement of a negative number is added to the last bit of its inverse to remove the highest carry
Ex. :
Using 32-bit binary representation, the complement of + 5 is equal to the original code, i.e. 0000 0000 0000 0000 0000 0101. The complement of + 5 adds 1 at the end of the inverse code, removing the highest carry. That is, 1111 1111 1111 1111 1111 1111 1111 1011
Find the source code according to the complement
After we know the concepts of source code, inverse code and complement above, we should already know the process of conversion from source code to inverse code. However, if we know the complement of a number, what about the operation of finding the source code?
In fact, we know that the operation of finding the source is to find the complement of this complement
If the sign bit of the complement is 0, indicating that it is a positive number, then its source code is its complement
If the sign bit of the complement is 1, which means that it’s a negative number, then you just take the complement again and its complement is the original
Ex. :
Find the complement 1001 is the source code of decimal -7
We take the complement again, that is, take the inverse and then add 1, take the inverse to get 1110, and then add 1 to get 1111. According to the source code of -7 above, it is 1111
Binary is stored in memory as complement
As mentioned above, at this point, the final conclusion is that binary numbers are eventually stored in memory in the form of complement. Now do you know why they are stored in complement? Did you GET it?
Using complement, we can easily transform the subtraction operation into addition operation, and simplify the operation process. The complement of a positive number is the truth value of the number it represents, while the numerical part of the complement of a negative number is not the truth value of the number it represents, so the result is still the complement
Different from the original code and inverse code, there is only one complement of value 0, which is 0000 with 4 bits as an example
Again, the difference between 32-bit, 12-bit, 8-bit and 4-bit is the value range of storage, just as the valid value range of 8-bit storage source code and inverse code is -127 ~ +127, the range of complement is -128 ~ +127, and the range of 4-bit source code and inverse code is -7 ~ +7. The complement ranges from -8 to +7, so you can see why JS has the concept of maximum and minimum significant digits
Of course, we’re only thinking about integers, not decimals, just to make it easier for us to understand the source code, the inverse code, and the complement code
Number storage in JavaScript
JavaScript is not a type language. Unlike many other programming languages, JavaScript does not have different types of numbers, such as integers, short, long, floating point, and so on
In JavaScript, numbers are not divided into integers and floating-point types, that is, all numbers are stored in floating-point type, which uses the 64-BIT floating-point format defined by IEEE 754 standard to represent numbers, as shown in the following figure
-
The 63rd bit is the first sign bit S (sign)
-
52-62 bits E (Exponent bias)
-
0 ~ 51 digits, 52 Mantissa
The sign bit, as I said above, is positive and negative, 0 is positive, 1 is negative
Sign bits are easier to understand, so what is mantissa and what is order code?
What is the mantissa
For the sake of illustration, let’s go straight to the mantissa of the decimal number 5.2
First, we transpose the integer part and the decimal part into binary, but repeat the process many times. The result is as follows
101.00110011.// The decimal part 0011 is infinite
Copy the codeThere are many ways to represent a floating point number, but the specification generally uses scientific notation, such as 101.00110011… , we will use 1.0100110011.. The * 2^2 expression, which leaves only one integer, is called normalization
There are only zeros and ones in binary. According to scientific notation, except for the digit 0, all normalized digits can start with only 1. IEEE 754 omitted this default 1 to increase the range of stored values, so the effective mantis actually has 52 + 1 = 53 bits
The mantissa represents the decimal part of a number, that is, the binary value 1.0100110011. * 2^2 ends with 0100110011… , because it is an infinite repeating decimal, so we can take the maximum 52, the rest will be truncated, which will cause a certain loss of accuracy, this is why JS 0.1 + 0.2! If the mantissa is less than 52 digits, add 0 after it
We might wonder why all numbers except 0 start with a 1. For example, 0.0101, a decimal with a value of 0 < 1, starts with a 0. We said it was normalized. So it’s not confusing to drop the first 1
What is order code
First of all, we need to know
Order = order true value + offset 1023, offset = 2^(K-1)-1, k represents the order number
The truth value of order code is the binary expression of the true value of the index in scientific notation, which indicates the position of the decimal point in the mantissa
So why do you add the truth of the order code to the offset to get the order code?
Simply understood, the order truth value is the binary value in the actual exponent, and the order code is the binary value saved after the exponent offset
Also take the above value 5.2, whose normalized binary is 1.0100110011.. * 2^2, 2^2, that is, the true value of the order code is 2, then plus the offset 1023 is 1025, after the binary 11 order code is 10000000001
So why offset?
Why does the step code have offset 1023?
Now, you might be wondering why there’s an offset in order code, but let’s just go through it. Okay
For an 11-bit order code, the range of binary values that can be stored by the order code is 0 ~ 2047, which becomes 1 ~ 2046 excluding the two normalization cases of 0 and 2047 (normalization will be said below). Here, it refers to the positive number, because there are negative numbers, then the exponential range is -1022 ~ 1023. If there is no offset, Exponent needs to introduce sign bit, because there are negative numbers, but also need to introduce complement, will undoubtedly make the calculation more complicated, in order to simplify the operation, use unsigned order code, and introduce the concept of offset
The order E in different cases
We mentioned above the concepts of normalization and de-normalization. What are they
The normalized case is actually the general case we mentioned above, because the order cannot be 0 or 2047, so the exponent cannot be -1023 or 1024, and only in this case will the mantissa have the implied bit 1, which is ignored by default, as follows
S + (E! =0&& E! =2047) + 1.M
Copy the codeSo normalization is a special case where the order codes are all zeros and the exponent is -1023. If the mantissa are all zeros, floating-point numbers represent plus or minus zeros, otherwise they represent numbers very close to 0.0, as follows
S + 00000000000 + M
Copy the codeNormalization means that the order codes are all zeros, which means that there is another case where the order codes are all ones and the exponent is 1024, in which case if the mantissa are all zeros then infinity, and if the mantissa is not zero then NaN
Infinity: S +111 11111111 + 00000000.NaN: S +111 11111111+ (M! =0)
Copy the codeTesting a ha
Let’s take a quiz to calculate the binary representation of the decimal number -15.125 in JS memory. Let’s try it out and see the answer after we finish
|
|
All saw this, move a small hand, point a praise 😄
|
|
As above, find the decimal number -15.125 binary in JS memory
First of all, since it’s a negative number, the sign is 1
Then, the integer part 15 of 15.125 and the decimal part 0.125 were transposed to binary respectively. The calculation process will not be described. The integer divided by 2 is arranged in reverse order, and the decimal multiplied by 2 is arranged in the whole order
The normalized result is 1.111001 * 2^3 according to science and technology law
Next, calculate the order code, 3 (order true value) + 1023 (offset) = 1026
Convert 1026 to an 11-bit binary of 100 0000 0010, which is the order code
The mantissa of the normalized result is 1110 01 when the decimal part of the integer 1 is removed. The mantissa of the normalized result is 1110 0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
Finally, splicing can be done
Sign bit + order code + mantissa1 10000000010 1110010000000000000000000000000000000000000000000000
Copy the codeNumeric range in JS
If you really understand the above, you will find that the range of numbers actually has two concepts, the maximum positive number and the minimum negative number, the minimum positive number and the maximum negative number
The final range of numbers is the minimum negative number ~ maximum negative number and the minimum positive number ~ maximum positive number
S represents positive and negative from the three dimensions of S, E and M, namely number symbol, order code and mantissa. The value of order code E is much larger than the number of mantissa M, so order code E determines the size and mantissa M determines the accuracy
So, we start with the analysis of order code E
Under normalization, when E is at its maximum value, 2046 (maximum order code) -1023 (offset) = 1023 (order code truth value), i.e. 011 11111111
From the index (true value of order code) derived from the maximum value of order code E, the value range we can get is -2^1023 ~ 2^1023, and the result is 8.98846567431158e+307 by using the JS index function math.pow (2,1023). So if the mantissa is 1.11111111… If you add 8.98846567431158 x 2 to the original index, it equals to 1.797693134862316e+308
MAX_VALUE = 1.7976931348623157e+308 It’s pretty close to what we estimated (because we normalized it to approximately 2 for simplicity, which is actually a little bit too high)
So the range of maximum positive and minimum negative numbers is as follows
1.7976931348623157 e+308 ~ -1.7976931348623157 e+308
Copy the codeIf this value is exceeded, then the number is too large and overflow occurs. In JS, Infinity or -infinity will be displayed, namely Infinity and infinitesimal. The scientific name is forward overflow
Under normalization, then under normalization, that is, the index is 0 (minimum order code) -1023 (offset) = -1023, i.e. 10000000001
From the exponent, we can conclude that the minimum value is 2^-1023, when if the mantissa is 0.00000… 001
If the mantissa is not zero, the 52 mantissa equals the decimal point and you can virtually move 51 to the right to get a smaller 2^-51, so the minimum value is 2^-1074. Math.pow(2,-1074) equals 5e-324
The JS minimum constant number.min_value is 5e-324
So the minimum positive and maximum negative range of numbers is as follows
5e-324 ~ -5e-324
Copy the codeIf a value smaller than the smallest number that can be represented is stored, it is displayed as 0 and the scientific name overflows in reverse
The range of integers in JS
Unlike numbers, numbers can have decimals, but integers are simply integers
We analyze from the mantissa M, the accuracy is at most 53 bits (including the normalized implied bit 1), the range of exact integers is actually the maximum value of M, namely 1.11111111… 111, which is 2^53-1, uses the JS function math.pow (2,53)-1 to compute the number 9007199254740991
So the range of integers is actually going to be
-9007199254740991 ~ 9007199254740991
Copy the codeWe can also use JS internal constants to get the maximum and minimum safe integers
Number.MIN_SAFE_INTEGER / / - 9007199254740991
Number.MAX_SAFE_INTEGER // 9007199254740991
Copy the codeThat’s exactly what we want
So let’s say if an integer is in this range, it’s a safe integer
Whether an integer is a safe integer can be verified using the built-in JS method number.isSafeInteger ()
The last
There have been times in the development process when we have looked for safe ranges of computation, and we have had to convert to string computation. We can also use open source libraries such as bignumber.js, math.js, etc
, thank you very much for reading, this article before start to write the most was stopped because of that I write this binary to get mentally, so we can look at it again if you don’t know much about, don’t be discouraged, if this description is not properly can also see below auxiliary understand articles in the references at the end of the link, if you have not, points out, thank you
Also welcome everyone to pay attention to the public number “not serious front end”, to a three, thank you
More exciting at github.com/isboyjc/blo…
Refer to the article
What are the generation, application, advantages and disadvantages of source code, inverse code and complement?
The interrelation between source code, inverse code and complement code
Algorithm How floating-point numbers are stored in memory
0.1 + 0.2 does not equal 0.3? Why does JavaScript have this “slutty” operation?
How to understand floating point in JS?