Binary conversion

Integer to binary

Integer to binary rules: divide by 2 take mod, reverse order, until the quotient is 0 stop;

// The number 45 is represented in binary. 45/2 = 22... 1 22/2 = 11... 0 11/2 = 5... 1 5/2 = 2... 1 2/2 = 1... 0 1/2 = 0... 1 in reverse order, so 45 to binary: 101101; Similarly, the conversion of binary integers to decimal should be done from right to left: 1*2^0 + 0*2^1 + 1*2^2 + 1*2^3 + 0*2^4 + 1*2^5 = 45;Copy the code

Decimal to binary

The rules of converting decimal to binary: multiply by 2, round, and arrange in order until the product is 1.

0.625 * 2 = 1.25 0.625 * 2 = 1.25 0.25 * 2 = 0.5 0.5 * 2 = 1 0.5 * 2 = 1 0.625 * 2 = 1.25 0.625 * 2 = 1.25 0.25 * 2 = 0.5 0.5 * 2 = 1 The conversion from binary decimal to decimal should be from left to right: 1*2^-1 + 0*2^-2 + 1*2^-3 = 0.5 + 0 + 0.125 = 0.625;Copy the code

Pay attention to the point

  • If the number is greater than 1 and is not an integer, its binary representation is a concatenation of the integer part and the fractional part, such as 45.625 to 101101.101.
  • When converting a signed value into binary, we need to introduce a sign bit at the beginning of the binary. For example, 45 to 8-bit binary should be 00101101, and -45 to 8-bit binary should be 10101101.
  • In js, values starting with 0 are recognized as octal, values starting with 0b are recognized as binary, and hexadecimal values starting with 0x.
console.log(010)   // 8
console.log(0b010) // 2
console.log(0x010) // 16
Copy the code

The storage of binary in memory

  • The original code

The computer keeps the original numbers, that is, numbers without either positive or negative, we call them unsigned numbers, but the actual numbers we use are both positive and negative, so we have the source code — the first left side of the binary is left empty as a sign bit, where 0 is a positive number and 1 is a negative number.

Therefore, if we use 4 bits to store binary in memory, we can represent values ranging from -7 to +7. The code table is as follows:

The decimal system binary The decimal system binary
+ 0 0000 0 1000
+ 1 0001 – 1 1001
+ 2 0010 2 – 1010
+ 3 0011 – 3 1011
+ 4 0100 4 – 1100
+ 5 0101 – 5 1101
+ 6 0110 – 6 1110
+ 7 0111 7 – 1111

Note that using the source code to represent binary is actually easier to understand, but there are two problems:

  1. There is a calculation problem, (+1) + (-1) is 1010 (-2), which is not what we know;
  2. +0 and -0 are the same value to us, but there are two different binary representations;
  • Radix-minus-one complement

As noted in the note above, there are two problems with using the source code to represent binary, so to solve problem 1, there is an inverse code;

The definition of the inverse code: the inverse code of a positive number is itself, and the inverse code of a negative number remains unchanged on the basis of its original code, and the remaining 0 and 1 are stored in reverse.

The inverse code table is as follows:

The decimal system binary The decimal system binary
+ 0 0000 0 1111
+ 1 0001 – 1 1110
+ 2 0010 2 – 1101
+ 3 0011 – 3 1100
+ 4 0100 4 – 1011
+ 5 0101 – 5 1010
+ 6 0110 – 6 1001
+ 7 0111 7 – 1000

It can be seen from the above inverse code table that the inverse code of -1 is 1110, so the value of (+1) + (-1) is 0001 + 1110 = 1111; The inverse code table 1111 is the representation of -0.

  • complement

If the inverse code solves only problem 1 of the source code, the complement code also solves problem 2 of the source code. The definition of complement: the complement of a positive number is itself, and the complement of a negative number is +1 on the basis of the negative number. The complement table is as follows:

The decimal system binary The decimal system binary
+ 0 0000 0 0000
+ 1 0001 – 1 1111
+ 2 0010 2 – 1110
+ 3 0011 – 3 1101
+ 4 0100 4 – 1110
+ 5 0101 – 5 1011
+ 6 0110 – 6 1010
+ 7 0111 7 – 1001

As shown in the complement table above, both +0 and -0 are 0000, thus perfectly solving the problem of having different binary expressions for +0 and -0.

Why is the negative code +1 of -0 0000? Because the above binary storage is stored in 4 bits, so when the result of 1111 +1 is 10000, the leftmost high part of the sign bit will be automatically discarded. At this time, the fourth sign bit has become 0, and the leftmost high part 1 will be discarded, so the complement of -0 is 0000.

When we take the negative’s complement, the smallest integer we can represent goes from -7 (1001) to -8 (1000), so the range we can take is from -8 to +7.

  • frameshift

There are two main functions of code shift:

  1. Convenient comparison of value size;
  2. Fixes for “order” in floating-point numbers (put that down for a moment);

The definition of shift code: complement other bits unchanged, the symbol bit is inverted.

We know that minus 2 is less than 2. However, in binary, -2 is 1010,2 is 0010, so the comparison will fail. However, after the sign bit is inverted with complement, -2 is 0010, 2 is 1010,1010 > 0010, so the correct comparison result can be obtained.

Q: Find the complement of -15

// We use 32-bit storage to represent the complement of the value 15. 1. Obtain the absolute value (15) from the binary code: 0000 0000 0000 0000 0000 0000 1111 2. Take the original code of -15, the sign bit is 1:1000 0000 0000 0000 0000 0000 0000 0000 1111 3. 1111 1111 1111 1111 1111 1111 1111 1111 0000 4. The complement code is the inverse code plus 1 1111 1111 1111 1111 1111 1111 1111 1111 0001Copy the code

conclusion

Binary numbers are eventually stored in memory in the form of complement; For positive numbers, the source code, the inverse code, and the complement are the same (its own source code)

JS

JS values are stored in the 64-BIT floating point format defined by the IEEE 754 standard

What is the IEEE 754 64-bit format?

As shown in the figure above, 1 sign bit (S) +11 bits of code (E) +52 bits of mantissus (M) make up a 64 bit double precision floating point number.

mantissa

When you normalize a binary floating point number, the fractional part of the number is the mantissa

Normalization is the representation of binary floating point numbers using scientific notation, such as binary 101.00110011 for 5.2… , which is 1.0100110011.. * 2^2 (move the decimal point left or right until the first digit to the left of the decimal point is 1), where 0100110011.. The part is the mantissa.

Note that in scientific notation, all numbers start with 1 except for 0, so the IEEE 754 standard omits the 1 by default, thereby increasing the range of mantissa stored values, so that a valid mantissa actually has 52 + 1 = 53 bits. This is why the maximum safe number for JS is 2 ^ 53-1.

exponent

An order is an unsigned integer used to weight a floating point number. The order = order truth + offset 1023, where the order truth bit is normalized to the value of the exponent in scientific notation, and the offset is 2^(k-1)-1, where k represents the number of code bits, such as the 8-bit order offset =127, and the 11-bit order offset is 1023.

Why is the offset of the 11-bit code 1023?

The order code is an unsigned integer, so it can store binary values between 0 and 2047. Excluding the two non-normalized values of 0 and 2047, its range is 1 to 2046, but the exponent in normalization may be negative, so you need to introduce an offset 1023 to change the range to -1022 to 1023. Otherwise, if you have negative numbers, you have to introduce the complement code, which will make the calculation more difficult.

What is the denormalization?

  • If the mantissa is 0, it means Infinity. If the mantissa is not 0, it means NaN. If the mantissa is not 0, it means NaN.
  • When the order code is 000, 0000, 0000 and the exponent is -1023, if the mantail is 0, it means positive or negative 0; otherwise, it is a number very close to 0.

Find the binary representation of -13.125 in JS memory?

  1. Because -13.125 is a negative number, we know that the sign bit is 1;

  2. Find the binary representation of 13 and 0.125 respectively: 11101 and 001, so the binary representation of 13.125 is 1101.001;

  3. After the above binary is normalized according to the method of science and technology, it is 1.101001 * 2 ^ 3, from which we know the mantissa is 101001;

  4. At this time, we can know that the truth value of the order code is 4, and the order code = the truth value of the order code + the offset 1023 = 3 + 1023 = 1026, so the binary of the order code is 10000000010;

  5. The binary representation of -13.125 in JS can be obtained by putting the symbol bit + order code + mantissa together (the mantissa less than 52 bits should be completed by 0) :

    1 100000000010 1010010000000000000000000000000000000000000000000000