I have never understood what is the original code, reverse code and complement code, and what is the function. After studying this article, I finally understand a lot. grateful!
1. Why do you need to reverse the code?
The one’s complement function is equivalent to the negative number in mathematics.
For elementary school students, the arithmetic problem they can do is: 5-3, but they can’t do 3-5. Therefore, when we were in junior high school, a new concept was introduced in mathematics: negative numbers. After the introduction of negative numbers, the original subtraction operation can be changed to addition:
3-5=3 + [-5]=[-2], the square brackets represent “negative numbers”, and “negative numbers” are artificial mathematical terms given by us.
For a computer, the arithmetic problem that can be done is: 5 + 3, but it cannot do 3-5. So, we introduced a new concept in coding: inverse code. After the inverse code is introduced, the operation that was originally a subtraction can be implemented as an addition:
3-5=3 + [-5]=[-2], the square brackets represent “inverse code”, and “inverse code” is a computer term given by us.
Here, you must have a question: why the computer can only do 5 + 3, but not 3-5. This is because there is only an adder in the digital circuit of the computer, and there is no so-called “subtractor”. It’s not that computer manufacturers can’t design subtractors, because smart people have invented a method that can use addition to implement subtraction, so why do they need to add a subtractor?
Then he said: So how to define the inverse code to realize the function of changing subtraction into addition? Smart people think of the following way:
1. The inverse code of a positive number remains the original code unchanged: 3=[0_0000011]
2. Negative numbers except the highest bit (sign bit), reverse all (0 to 1, 1 to 0): -5=1_0000101 inversion=[1_1111010 ]
So the calculation process of 3 + [-5]=[-2] is:
[0_0000011] + [1_1111010]=[1_11111101]
In this way, this inverse method successfully achieves its goal! As for why, I think only mathematicians can give an explanation.
Second, why do you need complement code?
It’s all because of the special number“0”.
Let me ask you a question first: Is 0 positive or negative? You will definitely say: 0 is neither positive nor negative. This is the mathematical knowledge we learned in junior high school. There is no problem with this answer, so every time 0 is encountered in the future, people will not treat it as a positive or negative number.
What about computers? The computer is different from the human brain. Before encountering any number, the computer only judges the positive or negative according to the sign bit of the highest bit. “0” means a positive number, and “1” means a negative number.
Earlier we deduced why one’s complement is used, so the range of positive numbers represented by 8-bit one’s complement: + 0 — + 127; the range of negative numbers: -127 — -0. However, there are two special encodings that appear:
[0_0000000]= + 0 (ones complement)
[1_1111111]=-0 (inverse code)
In fact, +0 and -0 both represent 0. In this way, the encoding of the number “0” in the computer is not unique. For a computer, this is absolutely not acceptable, since any number can only have 1 encoding.
Therefore, smart people made such a decision: treat 0 as a positive number, that is, + 0, so that the code of 0 becomes: 0_0000000. The positive range of the 8-bit binary representation is still: + 0 — + 127.
However, adjustments must be made for negative numbers, that is, -0 must give way — the code 1_1111111 cannot represent -0. We can “move the negative number by 1 bit” as a whole: as long as the range of negative numbers represented by 8-bit binary is changed from: -127 – -0 to: -128 – -1, the problem can be solved successfully.
So how to move 1 bit as a whole? The method is to invert + 1. {1_1111111} encoding no longer represents -0, but becomes -1. Pushing along, the smallest code {1_0000000} is -128.
We artificially gave this inverse code + 1 a new name called complement code. Thus, the definition of the complement code is as follows:
1. The complement of a positive number remains the original code unchanged: 3={0_0000011}
2. Negative numbers are complemented first, then plus 1: -5=[1_1111010] + 1={1_1111011}
So the calculation process of 3 + {-5}={-2} is:
{0_0000011} + {1_1111011}={11111110}
So far, the problem of the non-unique encoding of the number 0 in the computer has been successfully solved through complementation, and it can also realize subtraction into addition.
So, in the computer world, 0 is a positive number. This is different from the mathematics we learn.
{0_1111111}= + 127 (complement)
{0_0000000}= + 0 (complement)
{1_1111111}=-1 (complement code)
{1_0000000}=-128 (complement code)
3. Real machine demonstration
Having said so much, is the internal circuit of the computer based on our above theory? We must have a real machine demo to experience:
Default: AX=3,BX=5,CX=-5. DX is used to store operation results.
- Positive addition: AX + BX
MOV AL,3 MOV BL,5 ADD AL, BL MOV DL,AL
Save the assembler as code.asm and compile it into EXE with NASM:
Then debug with the Turbo-Debugger debugger:
Press F8 to debug step by step:
AX=3
It can be seen that AX, BX and DX are all original codes, that is, the complement of positive numbers is the original code.
2. Positive number subtraction: AX-BX
MOV AL,3 MOV BL,5 SUB AL, BL MOV DL,AL
It can be seen that after this subtraction, the result is 0XFE={11111110}={-2}, successfully verifying the previous inference:
So the calculation process of 3-5={3} + {-5}={-2} is:
{0_0000011} complement + {1_1111011} complement={11111110} complement
As I said before, the operation process of subtraction is to change subtraction into addition: 3-5={3} + {-5}, so here must first convert the value 5 of the subtrahend BX into the complement of -5, but We see that the value of BX is always 05 during the running of the program, and it has not become the complement of -5. What’s going on? Because subtraction to addition is only a calculation process of the CPU, it does not modify the value stored in the operand, you can understand that after the CPU takes 5 out of BX, there is a special circuit responsible for changing it to -5 Complement code, or there is a special hidden register to store its complement code, and then participate in the addition operation. The value of BX is 5, which is artificially given by us. Of course, it cannot be modified at will for such a subtraction.
3. Addition of positive and negative numbers: AX + CX
MOV AL,3 MOV CL,-5 ADD AL, CL MOV DL,AL
The figure below shows that the computer sees that CX is a negative number, and directly encodes it into a complement code for storage: 0XFB={11111011}={-5}. So how does the computer store CX=-5 as the complement code 0XFB? Is it necessary to strictly follow the steps we introduced before:
(a) positive original code = 00001001
(b) negative original code=10001001
(b) Negative code=11110110 (invert sign bit)
(c) Complement code:=complement code + 1=11110111=0XFB
This question will have a clear answer in the next section.
Negative numbers CX are stored directly as two’s complement
The result after the operation is as follows: the result is 0XFE={11111110}={-2}, the operation process is:
{3} + {-5}={-2}
4. Subtraction of positive and negative numbers: AX-CX
Operation result: 0X08={00001000}={8}, namely: 3-(-5)=3 + (-(-5))=3 + 5=8.
So the question is, how does (-(-5)) operate this computer? You will definitely say “negative negative is positive”, but the computer will not understand. Since all subtraction changes to addition, the rules are actually the same—take the opposite of the subtrahend and add:
A-B=A + (-B).
Then I just need to design a method that can calculate the opposite number of any number, and the method for calculating the opposite number by the computer is:
Negative number = inverse code + 1 : -B=~B + 1, where B can be any number, no need to distinguish between positive and negative and sign bit!
Therefore, the process of (-(-5)) is that the computer needs to take the opposite number twice for encoding:
(a) Encoding -5 for the first time — rule: [5’s complement] + 1=00000101 inversion + 1=11111011
(b) Encoding -(-5) for the second time — rule [inverse code of -5] + 1=11111011 inversion+ 1=00000101, actually returned to the encoding of 5, which is equivalent to “negative negative Get it right.”
Although they are all one’s complement + 1, this is different from the complement method of negative numbers we introduced earlier: when finding the negative number’s complement, the sign bit is excluded. And here to find the opposite number is to invert all the bits.
With the concept of opposite numbers in the computer, all algorithms can be unified: negative numbers are the opposite of positive numbers, and subtraction is the opposite of subtrahends and then added. Therefore, we can further optimize the stored procedure of CX=-5 in the previous section:
(a) The original code of 5 = 00001001
(b) Reverse all=11110110
(c) Complement code:=complement code + 1=11110111=0XFB
I think this is the real coding process of the computer, because it does not need to consider and judge the so-called “sign bit” of the first positive and negative sign when coding, as long as it sees the symbol “-“, repeat the “inverse code + 1“.
4. Negative subtraction
According to the above process, the most complicated negative number subtraction process can be inferred: such as AX=-3, BX=-2, we need to calculate the subtraction of these two negative numbers: DX=AX-BX, the process should be:
(a) AX is stored in the minuend: Since the computer sees a negative sign “-“, it is necessary to perform an inverse operation on 3: the original code 3 is inverted + 1: 00000011 inverted + 1=11111101= 0xFD.
(b) BX is stored in the subtrahend: Since the computer sees a negative sign “-“, it is necessary to perform an inverse operation on 2: the original code 2 is inverted + 1: 00000010 inverted + 1=11111110=0XFE .
(c) DX=AX-BX: The computer first converts subtraction into addition, AX-BX=AX + (-BX), since the computer sees that the second addend has a minus sign “-“, it needs to take BX once The operation of the opposite number: BX inversion + 1 = 11111110 inversion + 1 = 00000010.
(d) Calculate addition: AX + (-BX)=11111101 + 00000010=11111111=0XFF={-1}
The computer verification screenshot of the process is as follows:
Therefore, from the above process, it can be clearly seen that the most important thing for the computer is: “Inverse code + 1“, the inverse code + 1 is called complement code. With the complement code, the computer can realize the operation of the negative sign “-“, and this operation is actually the meaning of taking the opposite number.
It is the concept of negating the number, so there is such an instruction in the assembler: NEG. This instruction is to take the opposite number, which is also equivalent to performing a complement (one’s complement + 1) operation on the logarithm.
Complement code, the mechanism of negating numbers, brings too many benefits to the computer. In addition to preventing the computer from distinguishing between addition and subtraction, it does not need to distinguish between positive and negative numbers at the hardware level during addition and subtraction (the sign bit is not specially treated). For example, for a code: 0xF0, when it is stored in memory, if it is an unsigned number, it should be equal to 240; if it is a signed number, it should be equal to -16. So which number does it represent? At the hardware level, the computer does not need to know whether it represents 240 or -16, because whether it is positive or negative does not affect the addition and subtraction of any other numbers. For example, after adding the encoded value 0x02 of the number 2, the encoded value is 0xF2, then this encoded value can represent 242 or -14.
So which number does this 0xF0 represent in the end? This is something that programmers need to deal with. For example, you should define it as signed or not in C language. Next, we must illustrate this process with an example:
If you define a variable equal to -16 as signed char type, when we need to apply this variable in our program, such as printf(%d), the printf function in the C language standard library will first fetch the variable from the memory The value: 0xF0, because the variable is a signed type, it first judges that it is a negative number according to the sign bit of 0xF0 is 1, and the first step is to generate a “-” sign and put it at the first place of a temporary string. The remaining thing is to convert the code 0xF0 into the numeric string “16” corresponding to the decimal system. The key question is how does printf realize this conversion?
Through the previous deduction, we know:Negative numbers are the complements of positive numbers, and positive numbers are the complements of negative numbers, and they are opposite numbers. Now, we require the encoding of positive numbers. Of course, we only need to reverse the number once based on the complement of negative numbers. Therefore, the process of taking the negative number of 0xF0 will be as follows:
0xF0 Negative Number = 1111_0000 Negative Number = 11110000 Inverse Code + 1 = 00001111 + 1 = 0001_0000 = 16D
Although the value of 16 is obtained, it is different from the string “16”. In the end, printf needs to connect the “-” and “16” to form the complete string of this variable. How can the number 16 be converted into the string “16”?
The method is that we need to obtain bit by bit in the decimal data: first take out the highest digit 1, and then convert 1 into the character “1”; then take the lowest digit 6, and convert 6 into the character “6”. Since the ASCII code value relationship between each number x and their corresponding characters is: ASCII code = 48 + x. Therefore, we add 1 + 48=49, 6 + 48=54 to the obtained number, then we get two characters “1” and “6”. Printf connects the characters “1” and “6” to the character “-” in turn, and the final complete string is obtained: “-16”. Finally, printf calls the operating system string display API to completely display “-16” on the screen!
Through this case, we can see that the process of high-level language coding for the underlying computer is relatively not simple, so the high-level language will shield many details of the underlying computer.
Then the above 0xF0, let’s go further. Even the hardware level does not know whether 0xF0 represents a number (data) or a machine instruction. That is also something that programmers need to care about and design: when the program runs to the 0xF0 storage location in the memory, it should represent a machine instruction; and when the program needs to fetch the 0xF0 value from the memory, it It should represent a number (data).
Keep pulling back. Although it is not necessary to distinguish between positive and negative numbers when adding and subtracting at the computer hardware level, it is not necessary when multiplying and dividing. For example, now there is a dividend code: 0x01E0, and a divisor code: 0xF0. 0x01E0 represents the number 480. 0xF0 may represent 240 or -16. The calculation result is 480/240=2 or 480/-16=-30. The encoding of 2 is 0x02, and the encoding of -30 is 0xE2. Obviously, these two encodings cannot be unified (because the sign bit is involved in the calculation process), so you are in Before doing multiplication and division, it is necessary to specify at the hardware level whether 0xF0 represents a positive number 240 or a negative number -16. Because of this, Assembler must specify unsigned or signed multiplication and division when doing multiplication and division, use instruction: DIV for unsigned division, and instruction: IDIV for signed division.
Four. Summary
In the end, the three encodings of computer numbers—original code, inverse code and complement code, we can summarize in one sentence as follows:
Original code: It is a binary code for natural positive numbers (including 0), and positive numbers are directly stored in the computer using the original code.
Inverse code: It can be understood as the intermediate process of seeking complement code, inverse code = the original code is reversed bit by bit. Computers don’t store one’s complement.
Complement code: The computer code to find the opposite number, complement code = complement code + 1. Negative numbers are stored in computers using two’s complement.
But At the end of the day, we can say that computers store in two’s complement. Why? Because the original code = the complement of the corresponding opposite number, it is actually a complement, but it is the complement of a negative number.