One, foreword
The computer’s favorite numbers are 0 and 1. In the world of the CPU, they are the only two numbers it recognizes, and even powerful operating systems are made up of 0 and 1.
As a software developer, the beginning lesson might be to recognize these two simple and powerful numbers. But most people’s knowledge of binary, binary computation, source code, inverse code and complement is still in the stage of mechanical forced memory. Especially for some coding and calculation, is still in a vague understanding stage, such as:
How does the CPU represent negative numbers?
Why can complement be used to represent negative numbers?
Why is the minimum value of an 8-bit binary number -128, not -127?
CPU adder, why can be together with the symbol bit calculation?
This article will help you understand the basics of binary computing. After reading this article, you will not only know why, but also why!
PS: Here is a bit high profile, the final part, should involve the level of mathematical proof, this paper will not involve the verification process.
From decimal to binary
1. The decimal
As China has strong mathematical calculation ability, addition and subtraction within 10 should be completed in kindergarten. If you don’t fall into this category, you’re in a fake kindergarten.
Let’s quickly review some of the basics of decimal arithmetic:
Each digit contains digits from 0 to 9;
Each digit has 10 times the number of digits to its right;
When two numbers are added, if the sum of the numbers in the same place is greater than or equal to 10, it advances 1 place, that is: full decimal 1;
To be specific,
How many 1s are represented by the first digit from the right;
How many tens are represented by the second digit from the right;
How many hundreds are represented by the third digit from the right (hundreds);
How many 1000’s are represented by the fourth digit (thousands) from the right;
Decimal numbers can be represented by the suffix D or omitted. For example, the decimal number 1234 has 4 in the units place, 3 in the tens place, 2 in the hundreds place, and 1 in the thousands place (usually starting from the rightmost units place). Each digit in the decimal place is ten times larger than its right-hand side. The diagram below:
Decimal data, also known as ten – based representation.
2. The binary
What about binary? Just apply the decimal concept above and replace 10 with 2 (ignoring sign bits for now) :
Each digit contains digits 0 and 1;
Each digit has twice the number of digits to its right;
When two numbers are added, if the sum of the numbers on the same digit is greater than or equal to 2, it is 1 bit forward, that is: full two into one;
To be specific,
How many ones does the first digit from the right represent?
How many twos are represented by the second digit from the right;
How many fours are represented by the third digit from the right;
How many eights are represented by the fourth digit from the right;
A few important points to remember: binary numbers contain only two digits, 0 and 1, which are added into one.
In decimal, we give each digit its own name (ones, tens, hundreds…). , but binary has no similar naming.
The binary number is represented by the suffix letter B, for example: the binary number 1111B is represented by the following figure:
In decimal notation, this is 15(1 * 8 + 1 * 4 + 1 * 2 + 1 * 1 = 15).
In binary, each bit is called a bit. If eight bits are used to represent a binary number, the minimum value is 0000_00000 and the maximum value is 1111_1111.
If 16 bits are used to represent a binary number, the minimum value is 0000_0000_0000_0000 and the maximum value is 1111_1111_1111_1111. (For ease of observation, delimiters are added between each 4 bits.)
In early computers, 8-bit processors were so common that they were given a special name: Byte. A 16-bit binary number is two bytes, also known as a Word.
3. Expand to hexadecimal
The principle is the same: just replace 10 with 16 in decimal:
Each digit contains the numbers 0 through 9, A through F;
Each digit has 16 times the number to its right;
When two digits are added, if the sum of the digits in the same digit is greater than or equal to 16, the digit is advanced by 1 digit.
To be specific,
How many ones does the first digit from the right represent?
How many 16s are represented by the second digit from the right;
How many numbers does the third digit from the right represent 256;
How many numbers are represented in the fourth digit from the right 4096;
In hexadecimal, you need 16 numbers to represent 0 to 15 and those numbers, 0 to 9 are easier to deal with, but from 10 to 15, you need to find some notation, so people came up with the idea of using the letters A,B,C,D,E, and F to represent 10 to 15.
Hexadecimal data, represented by the suffix H or, in some cases, by the prefix 0x, is essentially indistinguishable. For example, the hexadecimal number 1A2BH (or 0x1A2B), with the weights on each digit as shown below:
In decimal, this is 6699(1 * 4096 + 10 * 256 + 2 * 16 + 11 * 1 = 6699).
4. Extend to any base
The principle is still the same: replace the 10 in decimal directly with the target base, such as base 5:
Each digit contains digits from 0 to 4;
Each digit has five times the number of digits to its right;
When two numbers are added, if the sum of the numbers on the same digit is greater than or equal to 5, it advances 1 digit, that is: full five into one;
To be specific,
How many ones does the first digit from the right represent?
How many fives are represented by the second digit from the right;
How many 25s are represented by the third digit from the right;
How many digits in the fourth digit from the right represent 125;
Let’s look at another picture to deepen our impression:
Three, from decimal addition to binary addition
1. Decimal addition
That goes without saying, there are only two rules:
The addition of two numbers in the same place;
The sum of each digit is one decimal;
Such as:
In the ones place: 4 + 8, the result is 12, but there is no such number as 12 in decimal, so if you carry the left high place by 1, you are left with the ones place: 12-10 = 2.
In the tens place: 7 + 2, plus the carry 1, the result is 10, but there is no decimal number 10, so carry 1 to the left, the tens place becomes: 10-10 = 0.
In the hundreds place: 1 plus carry 1 is 2.
2. Binary addition
Bit 0:0 + 0 result is 0;
1st place: 1 + 0 result is 1;
The result is 2, but there is no 2 in binary, so we have to carry 1 to the high left, so we are left with 2-2 = 0 in the second bit.
Third bit: 1 + 1 equals 2, plus carry 1, the result is 3, but there is no 3 in binary, so we have to carry 1 to the left, so we are left with 3-2 = 1 in the third bit.
This is true for digits 4, 5, 6, and 7.
3. Hex addition
The 0th bit: E + C, the result is 26, but there is no hexadecimal number 26, so we need to carry 1 to the high left, so the 0th bit is left with 26-16 = A.
1: A + 1 = B, plus carry 1, the result is C, 16 mechanism has this number.
4. Convert negative numbers into positive numbers
1. The original code
True form is a binary fixed-point representation of numbers in a computer. The original code representation adds a sign bit (that is, the highest bit is the sign bit) to the front of the number: the positive bit is 0, the negative bit is 1 (0 is represented in two ways: +0 and -0), and the remaining bits indicate the size of the number.
For example, if a number is represented by 8 bits (8-bit binary number), the source code for +11 is 0000_1011, and the source code for -11 is 1000_1011.
2. Turn negative calculations into positive ones
We all know that CPU adder, like never heard of “subtracter”. For example, calculate 5 + 8 and convert it to binary to calculate:
Let’s calculate the subtraction again: 5-8. For the CPU, it only computes 5 + 8, but not 5-8.
But we could switch the idea, and we could add 5 + (-8), and we could calculate it. So computer pioneers invented inverse code:
The inverse of a positive number: keep the original code unchanged;
The inverse of negative numbers: the sign bits in the original code remain unchanged, and the rest are all reversed (the original code of -8 is 1000_1000, and the inverse code is 1111_0111);
So the calculation of 5 + (-8) is:
At this point, the subtraction problem is solved perfectly, and the multiplication (more) and division (more subtraction) problems are solved. As for how to prove it from a mathematical point of view, ask those mathematicians!
3. New question: How to represent 0?
We can now summarize the representation range of inverse codes (remember: the first is the sign bit) :
Positive numbers range from 0000_0000 to 0111_1111, that is, the 128 numbers from +0 to +127 in decimal notation.
The range of negative numbers: 1000_0000 ~ 1111_1111, that is, the 128 numbers of -127 ~ -0 in decimal;
Have you found the problem: why do the numbers +0 and -0 exist? And their codes are different: +0 for 0000_0000 and -0 for 1111_1111.
The CPU is a fool and will do whatever it is told, but the last thing the CPU can tolerate is uncertainty! We all know that +0 == -0 == 0, they’re the same number, but in binary code, there are two codes for the same number.
The great computer pioneers again made the decision that positive numbers remain the same and negative numbers are subtracted by one.
In other words: the sign bit is unchanged, the value of the whole plus 1, as follows:
This successfully solves the -0, +0 problem!
An 8-bit binary can now represent a range of -128 to 127 without any duplicate or missing digits.
Since the value of each binary representation has changed, it is no longer accurate to call them inverse codes, so they are given a new name: complements. In other words, the figure above looks like this:
To summarize the definition of complement:
Complement of positive numbers: keep the original code unchanged;
The complement of negative numbers: the sign bits in the original code remain unchanged, and the rest are reversed first and then added by 1(for example: the original code of -8 is 1000_1000, and the complement is 1111_1000);
At this point, we only solved the representation problem of the two-level coding, then: can complement directly participate in the operation? What can go wrong with the results?
4. Calculation of complement codes
Let’s start with this question: Let’s say the time is 1 o ‘clock sharp, but your watch has water and it says 3 o ‘clock sharp. Now how do you change the time to 1 o ‘clock?
Method 1: turn the clockwise counterclockwise for 2 hours (3-2 = 1);
Method 2: Turn the clock clockwise for 9 hours until 12 o ‘clock, and then for another hour (3 + 10 = 1).
For the clock dial, every 12 hours is a circle, can be considered: -2 == 10, -1 = 11, -3 = 9, the same: -2 == 10, -2 == 22, -2 == 34,…
The pattern is that the modulo of the numbers -2, 10, 22 and 34 gives the same number (positive). In mathematics, two integers are congruent if they are divided by “the same integer”.
12 in the dial is the “same integer”, and you can see that this is an “overflow” system. The numbers -2, 10, 22 and 34 represent the same number on the dial, so the integers are congruent.
In other words, the number 10, 22, 34 can be used to replace -2, and the result is the same.
So for an 8-bit binary number, there are only 8 bits at most, and in the calculation, if the highest bit produces a carry, it is discarded, so it is also an “overflow” system. So what is the same integer here?
As you can see from the previous section, the 8-bit binary numbers represented by the complement are in the range of -128 to 127, which is a total of 256 numbers, so if you modulo 256 and get the same remainder, then these numbers are the congruences.
For example, if you take the modulo of -2 and 254 to 256, you get the same remainder, so they are congruent, and 254 can be used instead of -2 in the calculation.
So let’s verify that by calculating 3 plus minus 2.
(1) Use the congruent number to calculate
3 + (-2) == 3 + 254 = 257
257 exceeds the maximum representation range, so it overflows, and the result is 257 modulo 256, which is 1.
(2) Directly use the complement code to calculate
The complement of 3 is 0000_0011, and the complement of -2 is 1111_1110.
The result is also 1, which means:
In binary computation, the congruence theorem is “naturally” satisfied by the use of complement codes.
Careful readers may have noticed that the binary complement representation of -2 is of the same form as the binary natural representation of 254!
This “natural” nature, is it a coincidence? Or the design of computer pioneers? !
Five, the summary
In this article, we explore the software cornerstone of computer systems: binary systems. The main purpose is to help you understand the representation and calculation of binary systems.
I hope you will be enlightened after reading it! If it is helpful to your understanding, please forward it to your technical partners and grow together!
Thank you very much!
Star mark public number, can find me faster!
1. C language pointer – from the underlying principles to fancy skills, with graphics and code to help you explain thoroughly 2. Step by step analysis – how to use C to achieve object-oriented programming 4. 5. It is said that software architecture should be layered and divided into modules, and what should be done specifically (2)