Why are negative numbers in computers stored in two's complement?

The use of two's complement storage for negative numbers in computers can simplify the basic computer arithmetic circuits, so that addition and subtraction only need to be implemented with addition circuits, and addition is used instead of subtraction. The complement is the smallest positive congruent remainder of a negative number, so adding a negative number and subtracting a positive number can both be represented by adding a complement.

The operating environment of this tutorial: Windows 7 system, Dell G3 computer.

1. Introduction

Do you know how integers are stored in computers? Is it the sign bit plus the value bit? Are the value bits stored in normal binary format?

If you answer yes to the last two questions, it means that when stored in 3-bit binary and the sign bit 0 represents positive and 1 represents negative, 1 will be stored as 001 , -1 will be stored as 101. Unfortunately, this is not the case. Computers store integers in the form of two's complement instead of the natural-looking form just now. Although the two's complement is also represented by the sign bit plus the value bit, the rules of expression are different: 1 will Save as 001, -1 will be saved as 111.

If you answered all three questions correctly, you know that integers are stored in two's complement format in computers, but do you know why this format is used? And "The complement of a positive number is equal to the original code; the complement of a negative number is equal to the complement plus 1, and the complement is equal to the sign bit of the original code unchanged, and the remaining bits are inverted." What does such a complement mean? What? (Assuming you don’t know, please read on XD)

Let’s first look at the purpose of using complement codes, and then forget about the definition of complement codes above. Start with this purpose and explore the essence of complement codes step by step. .
Purpose: In order to simplify the basic computer operation circuit, addition and subtraction only need to be implemented through the addition circuit, that is, subtract a positive number or add a negative number Such operations can be used Add a positive number instead. So the storage form of negative numbers is changed and stored in a form that can be directly added as positive numbers. This form is the complement code. (Positive numbers do not need to be changed, so positive numbers are generally omitted in the following discussion)

2. How does the complement code turn subtraction into addition?

2.1. Use the clock to understand subtraction to addition

This is an example around you. When you proofread the clock, suppose You find that the clock is at 6 o'clock, but it is actually only 2 o'clock now, that is, it is running 4 hours faster. You can correct it in two ways, one is to turn it back 4 hours counterclockwise to 2 o'clock, and the other is to set the clock back 4 hours to 2 o'clock. It is to dial 6 hours clockwise to 12 o'clock and then dial 2 hours, that is, dial 8 hours clockwise to 2 o'clock. So for the clock dial, suppose -N means turning N hours counterclockwise, N means turning N hours clockwise, then -4 = ​​8, there will also be -1 = 11, -5 = 7, and even -4 = ​​8 = 20 = 32 = -16. ..

What rules are hidden here? In fact, in mathematics, -4, 8, 20, 32, -16 can be classified as the same type of numbers that meet certain conditions - for modulo 12 congruence.

The definition of modulus and congruence on the Chinese Wiki is: two integers a and b, if the remainders obtained by dividing them by a positive integer m are equal, then a and b are said to be congruent modulo m. .

In an overflowable counting system, if the capacity of the counting system is taken as the modulus, then all numbers that are congruent to this modulus will have the same representation in this counting system, and the operations will be equivalent.
For example, the clock dial in the above example is an overflow counting system, the modulo is 12, so -4, 8, 20, 32, -16These numbers that are congruent to modulo 12 are on the clock dial The expressions above are the same, and the results of these operations on the hour hand are also the same, they will all be set to the same position.

A counting system composed of n-bit binary will discard the overflowing high bits, so it is also an overflowable counting system, and its modulus is \(2^n\). (Counting from 0 to \(2^n -1\), any more will overflow)
It can be inferred that in a counting system composed of 3-bit binary modulo 8, -2, - 10, 6, 14 can be represented by the same binary number. Subtracting 10 and adding 14 at the same time will get the same result.

2.2. Deriving the complement code

So, as long as the complement code is the positive congruent remainder of a negative number, then addition can be achieved This positive congruence complement has the same result as adding another negative number. For a negative number, there are countless positive congruences that meet the conditions. In order to reduce unnecessary operations, it can be specified that the complement is the smallest positive number among them.

Maybe because finding the complement code through the original code is a complementary modulo operation, it is called the complement code.

Note that the complement codes here are all marked by me with special marks, because this is not the real complement form stored in the computer. It should be called the complement number, but believe me, it is very close.

3. Improve the complement code

3.1. There are still some problems with this complement code representation

By converting to two's complement, subtracting a number does become adding a number. It seems very good, but there is an obvious problem, that is, the sign of the number itself is lost.
For example, 3-digit binary normally represents 0~7. Using the complement method, it can replace the operation of -8~-1, but it cannot truly represent - 8~-1, because you don't know whether it is a positive number or a negative number.
We converted negative numbers into a form that is more palatable to computers in calculations, but it lost its own information as a number.

How to solve this problem? Some people may quickly slap their heads: Then add one digit to indicate positive or negative. But what should I do when calculating in this case? Should I start counting from the second digit? When carrying out bits, do we need to pay special attention not to affect the sign bit? You will find that the problem is not that simple.

3.2. How to improve the complement code

I don’t know how Daniel came up with the idea, but the problem was solved perfectly:

• Under the premise of maintaining the characteristics of the complement code (that is, subtracting a number still becomes adding a number)
• Increase the expression of positive and negative (can truly represent -8~-1, just look at whether the sign bit is 0 or 1)
• can also make the operation without distinguishing the sign bit, directly treating the sign bit as the value bit for calculation, and the positive and negative sign of the result It will naturally conform to this positive and negative representation (that is, the carry of the sign bit and the carry of the value bit will be naturally reasonable)

And the solution is really skinny, surprisingly simple, that is, the previous The idea you thought of: Add one digit to indicate positive and negative.
The specific method is: Add a sign bit to the high position on the left. This sign bit, together with the pseudo-complement code we deduced earlier, forms a truly perfect complement code.
Achieved effect: By reading the sign bit, you can know the sign of the number. At the same time, the sign bit participates in the operation, carry, and carry out like the value bit in the addition operation.

4. Finally

summarize

• The purpose of using complement code: to simplify the basic computer operation circuit, So that addition and subtraction only need to be implemented with an addition circuit, and addition is used instead of subtraction.
• Why the complement code can achieve this purpose: n-bit binary can form an overflowable counting system. In such a system, the capacity of the counting system is used as the modulo, and all modulo are congruential to this The numbers will have the same representation in this counting system, and the operations are equivalent. The complement is the smallest positive congruent remainder of a negative number, so adding a negative number and subtracting a positive number can both be represented by adding a complement.
• How to calculate the complement: The complement of a positive number is itself; for a negative number, find the smallest positive congruence (modulo the capacity of the value bit) and put it into the value bit, with the sign position being 1 , get the complement of a negative number.

If you want to read more related articles, please visit PHP Chinese website! !

The above is the detailed content of Why are negative numbers in computers stored in two's complement?. For more information, please follow other related articles on the PHP Chinese website!