The surface of the work

In daily work and study, I often detect my bottom line. Whether computer foundation is good or not can completely determine a person’s code level and bug rate. I believe that you have learned these knowledge, but not for a long time to forget, today with you to review.

In line with the principle of easy to understand, this topic is explained clearly today.

Let’s talk about the very general question, why 0.1 + 0.2! Before introducing this issue formally, there are a few things you need to know about it.

  • The representation of computer binary and the calculation method of binary?
  • What is the original code, complement code, inverse code, shift code, are used to do what?

These are almost enough to understand the normal 0.1 + 0.2! == 0.3 problem.

The first pre-knowledge, binary

We know that in everyday life, there are many kinds of data presentation, including our daily routine use of base 10, CSS color representation of the hexadecimal, computing binary.

Binary representation

In a computer, all calculations are done in binary form, that is, all numbers are zeros or ones. Let’s take base 10 for example.

  • A decimal 1 is represented as 1 in a computer
  • 2 in base 10 is represented as 10 in a computer
  • 8 in base 10 is represented as 1000 in a computer
  • Base-10 15 is represented on a computer as 1111

Binary computing

For binary calculation, we are divided into two cases, one is the integer calculation, one is the decimal calculation.

Binary computation of integer parts

Let’s first explain how to convert base 10 to binary. The method of converting base 10 to binary is called “mod by 2”, in which you take a base 10 number and divide it by 2 to get the rest of the digits. Let me give you two examples

30% 2 · · · · · · · · · 0 15% 2 · · · · · · · · · 1 7% 2 · · · · · · · · · 1 3% 2 · · · · · · · · · 1 1% 2 · · · · · · · · · 1 0Copy the code

The binary conversion of integers reads from the bottom up, so the binary representation of 30 is 11110.

100% 2 · · · · · · · · · 0 50% 2 · · · · · · · · · 0 25% 2 · · · · · · · · · 1 12% 2 · · · · · · · · · 0 6% 2 · · · · · · · · · 0 3% 2 · · · · · · · · · 1 1% 2 · · · · · · · · · 1 0Copy the code

The binary conversion of integers is read from the bottom up, so the binary representation of 100 is 1100100.

I also wrote a function to convert this binary.

function getBinary(number) {
  const binary = [];
  function execute(bei) {
    if (bei === 0) {
      return ;
    }
    const next = parseInt(bei / 2.10);
    const yu = bei % 2;
    binary.unshift(yu);
    execute(next);
  }
  execute(number);
  return binary.join(' ');
}
console.log(getBinary(30)); / / 11110
console.log(getBinary(100)); / / 1100100
Copy the code

Next, let’s see how to convert binary to base 10. In plain English, it means multiplying every binary number from right to left by the corresponding power of 2 and increasing. For example, let’s take the top 100. The binary representation of 100 is 1100100. What we need to do is:

1100100
= 1 * 2^6 + 1 * 2^5 + 0 * 2^4 + 0 * 2^3 + 0 * 2^2 + 0 * 2^1 + 0 * 2^0
= 100
Copy the code

Simple and clear, needless to say, look at the implementation code:

function getDecimal(binary) {
  let number = 0;
  for (let i = binary.length - 1; i >= 0; i--) {
    const num = parseInt(binary[binary.length - i - 1]) * Math.pow(2, i);
    number += num;
  }
  return number;
}
console.log(getDecimal('11110')); / / 30
console.log(getDecimal('1100100')); / / 100
Copy the code

Binary computation of fractional parts

The binary calculation of decimal parts is different from the binary calculation of integer parts. The calculation of decimal parts to binary decimals is called the “double and round method”, which is to multiply a decimal number by 2 and take its integer part until its decimal part is 0. Here’s an example:

0.0625 * 2 = 0.125 · · · · · · · · · 0 0.125 * 2 = 0.25 · · · · · · · · · 0 0.25 * 2 = 0.5 · · · · · · · · · 0 0.5 * 2 = 1.0 · · · · · · · · · 1Copy the code

And the direction of reading the decimal part is also different. The binary conversion of decimals is read from the top down, so the binary representation of 0.0625 is 0.0001. This is exactly divisible, and in many cases it is not, such as 0.1 and 0.2 in the question. Write a function to convert:

function getBinary(number) { const binary = []; function execute(num) { if (num === 0) { return ; } const next = num * 2; const zheng = parseInt(next, 10); binary.push(zheng); execute(next - zheng); } execute(number); return '0.' + binary.join(''); } the console. The log (getBinary (0.0625)); / / 0.0001Copy the code

Try converting a decimal from a binary decimal to a decimal decimal, because we multiply, so we have division over here, and binary division can also be expressed as a multiplication of negative exponents, like 1/2 = 2^-1; Let’s see how 0.0001 is converted to 0.0625:

0.0001 * 2 = 0 0 * 2 ^ - ^ 1 + 2 + 0 * 2 + 1 * 2 ^ ^ - 3-4 = 0.0625Copy the code

So let’s implement this as a function.

function getDecimal(binary) { let number = 0; let small = binary.slice(2); for (let i = 0; i < small.length; i++) { const num = parseInt(small[i]) * Math.pow(2, 0 - i - 1); number += num; } return number; } the console. The log (getDecimal (' 0.0001 ')); / / 0.0625Copy the code

This is where the binary conversion comes in. For 0.1 + 0.2! The == 0.3 problem, the binary part above, is basically enough. Of course, the code part is only for reference, the boundary and other problems did not deal with…

Make a question to consolidate:

What is the binary representation of 18.625?? = >Click for details 
The binary of 18 is 100010. The binary of 0.625 is 0.101. Therefore, the binary of 18.625 is 100010.101

The second pre-knowledge, computer code

We know that computers use binary to calculate, when it comes to computer codes, we have to mention IEEE standards, and when it comes to decimal operations, we have to mention the STANDARD number of IEEE binary floating-point arithmetic standard (IEEE 754). Its standard binary representation is

V = (-1)^s * M * 2^E
Copy the code
  • Where S is the sign bit, 0 is a positive number, and 1 is a negative number.
  • M is mantissa, is a binary decimal, which stipulates that the first digit can only be 1,1 and the decimal point is omitted;
  • E is the exponent, or order code

Why are the 1’s and the decimal place omitted? Since all the first digits are 1’s, you can add one more digit to the end to increase accuracy. If the first digit is 0, it doesn’t mean anything.

In general, today’s computers support floating-point computations of both precision. One is float and the other is double.

format The sign bit mantissa exponent The total number Offset value
Single precision 1 8 23 32 127
double 1 11 52 64 1023

Take JavaScript as an example. Js uses a double precision format for calculation, and its floating point number is 64 bits.

The original code

What is a source code? A source code is the simplest, that is, the sign bit plus the absolute value of the truth value, that is, the first bit represents the sign and the rest represents the value. We use 11 bits as follows:

  • +1 = [000 0000 0001
  • -1 = [100 0000 0001] original

Because the first bit is a sign bit, the value range is [111 1111 1111, 011 1111 1111] = [-1023, 1023].

Radix-minus-one complement

What is an inverse code? An inverse code is an inversion based on the original code. The inverse of a positive number is itself; The inverse of a negative number is the same sign bit and the other bits are reversed.

  • +1 = [000 0000 0001] = [000 0000 0001
  • -1 = [100 0000 0001] = [111 1111 1110

complement

What is complement code? Complement code is complement on the basis of inverse code. The complement of a positive number is itself, and the complement of a negative number is added to its inverse by 1.

  • +1 = [000 0000 0001] Original = [000 0000 0001] inverse = [000 0000 0001] complement
  • -1 = [100 0000 0001] Original = [111 1111 1110] inverse = [111 1111 1111 1111] p

Why is there such a thing as complement?

  • First of all, in a computer there’s no subtraction, it’s all addition, so 1 minus 1 in a computer is 1 plus minus 1.

  • If subtracting using source code:

    1 + (-1) = [000 0000 0001] original + [100 0000 0001] Original = [100 0000 0010] Original = -2Copy the code

    Conclusion: Not true

  • To solve this problem, we have inverse code to do subtraction:

    1 + (-1) = [000 0000 0001] inverse + [111 1111 1110] inverse = [111 1111 1111] inverse = [100 0000 0000] original = -0Copy the code

    Found that the value is correct, but the sign bit is wrong; Although +0 and -0 are understood in the same way, 0 with a sign is meaningless, and there are both [000 0000 0000] and [100 0000 0000] encoding.

    ===>>> Conclusion: Not good

  • To solve the problem caused by the above notation, there is a complement to do the subtraction:

    1 + (-1) = [000 0000 0001] complement + [111 1111 1111] complement = [000 0000 0000] complement = [000 0000 0000] original = 0Copy the code

    The result is perfect, with 0 represented by [000 0000 0000] and not [100 0000 0000].

    Conclusion: Perfect

frameshift

Shift code, which is obtained by inverting the sign bit of the complement, is generally used as the order code of floating point numbers, and is introduced to ensure that the machine zeros of floating point numbers are all zeros. This is not positive or negative.

  • +1 = [000 0000 0001] Original = [000 0000 0001] inverse = [000 0000 0001] complement = [100 0000 0001] shift
  • -1 = [100 0000 0001] Original = [111 1111 1110] inverse = [111 1111 1111] complement = [011 1111 1111] shift

A little more attention can be paid to the pattern:

  • +1 = [000 0000 0001] = [100 0000 0001] shift
  • -1 = [100 0000 0001] original = [011 1111 1111] shift

Why 0.1 + 0.2! = = 0.3?

Back to our problem, let’s see why 0.1 + 0.2! Let’s look at the binary representation of 0.1 and 0.2.

0.1 = 0.0 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011.... 0011 Infinite loop 0.2 = 0.0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011.... 0011 Infinite loopCopy the code

We can see that 0.1 and 0.2 are both binary decimals with an infinite loop of 0011.

We know from above that floating point numbers in JavaScript are represented by 64 bits. How about 0.1 and 0.2 in computers?

0.1 = (-1)^ 0 * 1.1 0011 0011 0011 * 2^(-4) -4 = 100 0000 0100Copy the code

According to IEEE 754 standard:

V = (-1)^S * M * 2^E S = 0 // 1 bit, positive number 0, Negative 1 E = [100 0000 0100] original // 11 bits = [111 1111 1011] inverse = [111 1111 1100] Complement = [011 1111 1100] shift M = 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 // 52 digitsCopy the code

Similarly, 0.2 represents:

0.2 = (-1)^ 0 * 1.1 0011 0011 0011 * 2^(-3) -4 = 100 0011 0011 V = (-1)^S * M * 2^E S = 0 // 1 bit, positive number is 0, Negative 1 E = [100 0000 0011] Original // 11 bits = [111 1111 1100] inverse = [111 1111 1101] Complement = [011 1111 1101] shift M = 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 // 52 digits (including 1 decimal point)Copy the code

When you add them, the order code is different, so we need to do the order operation.

To order

There will be mantissa movement in pairs of orders.

  • The mantissa of the large order code is aligned with the small order code, so it is necessary to move the mantissa of the large order code to the left. At this time, the high part of the mantissa may be removed in the process of shift, which causes data errors. This is not desirable
  • If the small order code is aligned with the large order code, it is necessary to move the number of the small order code to the right and add 0 in the high order. This will crowd out the data on the right, which will affect the accuracy of the data, but will not affect the overall size of the data.

Computers take the latter, smaller approach. And that’s where today’s problem comes in, the loss of precision.

So now, let’s look at this movement up here.

// 0.1e = [100 0000 0011] original = [111 1111 1100] inverse = [111 1111 1101] p M = 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 // M = 0100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 / / mobile / / 0.2 remain unchanged after the original = E = [100, 0000, 0011] [111, 1111, 1100] anti = [111, 1111, 1101] / / 11, Unchanged M = 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 // 52 bits, unchangedCopy the code

The above is the binary result of the logarithm of 0.1 and 0.2. It is a bit difficult to calculate this number, so let’s directly calculate the truth values of 0.1 and 0.2.

True value calculation

0.1 = 0.0 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011.... 0011 Infinite loop 0.2 = 0.0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011.... 0011 Infinite loop 0.1 + 0.2 = 0.0001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 (1001... + 0.0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 (1100... Discard) = 0.29999999999998Copy the code

This is fucking wrong!!

The value we get when the browser is running is:

0.1 + 0.2 = 0.30000000000000004
Copy the code

The reason for the above problem is that there will be rounding during computer calculation. As seen above, the value discarded after the truth value is 1100. In computer, there will be rounding to 1, which is as follows:

0.1 + 0.2 = 0.0001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 (1001... + 0.0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 (1100... Discard) = 0.0100 1100 1100 1100 1100 1100 1100 1100 1100 1101 (enter 1) = 0.30000000000000004Copy the code

Here, we will talk about this part of the clear, if there is any wrong, welcome to point out. Thanks for reading.

The public,

[Delai ask front end], welcome attention, the first article in the public number above.

In addition to collecting selected articles from the community on a daily basis, we will also share technical articles from time to time.

I hope we can study together and make progress together.