1. Sign-magnitude

Sign-magnitude is a binary fixed-point representation method for numbers in computers.

To perform calculations, computers must store numerical values. The simplest way is to use machine code as our true value. For example, an 8-bit storage unit can store 256 different numbers from 00000000 to 11111111, representing true values from 0 to 255.

However, this design is not meaningful because we need to calculate negative numbers. To introduce negative numbers, the Sign-magnitude was designed: using the first bit of the storage unit to represent the sign, 1 for negative and 0 for positive, and the remaining bits to represent the absolute value of the true value. Similarly, using an 8-bit storage unit as an example, we can still represent 256 numbers using the Sign-magnitude method, ranging from 11111111 to 01111111, with a true value range of -127 to 127.

You may notice that there are only 255 possible true values, because both 10000000 and 00000000 represent 0.

From the binary of the true value to the sign-magnitude, we can see that there is no difference for the machine. It is just that we give the same binary number different meanings through mathematical methods, so that the computer can meet our calculation needs. Following this idea, we can also understand the one’s complement and the two’s complement.

2. One’s Complement

From the binary of the true value to sign-magnitude, we took a step forward and introduced negative numbers in the computer.

But there is a serious problem with sign-magnitude:

-1₁₀ is binary 10000001₂
1₁₀ is binary 00000001₂

As you know,

1 + 1 = 2

But 1000 0001 + 0000 0001 = 1000 0010

According to the rules of sign-magnitude, 1000 0010₂ == 2 ₁₀

This obviously does not work, and the circuit cannot be designed. For humans, it is easy to tell if the first digit is a sign bit, and we choose whether to add or subtract the absolute value of the subsequent digit and get at a result based on the sign.

But for a computer it is very complicated to separate the sign bit, and if we make the circuits for basic addition, subtraction, multiplication and division operations very complicated, then the performance of the computer is obviously very poor.

Now the problem is how to make the sign bit can participate in the operation and form a perfect logic.

To solve this problem, we introduced One’s Complement, which is defined as:

If the number is positive, it remains unchanged,
If the number is negative, it is inverted by bit except for the sign bit.

See the following figure for details.

Through the design logic of One’s Complement, we can find that the positive and negative numbers are now added to obtain 1111, which is -0. Now we have the ability to design the circuits and then use the computer to store and calculate.

3. Two’s Complement

One’s Complement solves the problem of signed bit operations, but there is still a problem that is not solved, that is, now we have two zeros, one +0 and one -0, which are mathematically indistinguishable and take up two codes. To solve this problem, the Two’s Complement was introduced.

The definition of Two’s Complement is that Two’s Complement of a positive number and 0 remains the same, and Two’s Complement of a negative number is the inverse of the corresponding positive number by bit and then +1.

A negative number can also be said to be the One’s Complement +1.

For example:

Also take 8 as an example of a storage unit, Sign-magnitude of -1₁₀ is 10000001 and One’s Complement is 11111110, Two’s Complement is One’s Complement +1, which is 11111111.

As you can see from above figure, -0 is the same as 0 after taking two’ complement, solving the problem of two zeros.

After -1 to -7, there is an additional code 1000 that can be used to represent -8, which is how we use computers today to store and compute.

4. How Does Two’s Complement Work ?

In two’s complement figure above,  we can also get -8₁₀ == 1000_2^.  Why ?

4.1 Congruence ( The Same Reminder )

Let us look at the clock below.

 

The pointer on the dial is pointing to 8. If I want to adjust the pointer to point to 1, what should I do?

1. Turn it clockwise for 5 hours (8 + 5) mod 12 = 1.
2. Turn it counterclockwise for 7 hours (8 - 7) mod 12 = 1.

For a dial, it makes no difference whether we turn it clockwise for 5 hours or counterclockwise for 7 hours. In fact, we can turn it clockwise for 5 + 12n hours or counterclockwise for 7 + 12n hours. From a different perspective, if the pointer is pointing to 8, we cannot tell whether it is 8 o’clock in the morning or 8 o’clock in the evening, based solely on the dial.

From the above phenomenon, we can draw two conclusions:

1. If we regard clockwise rotation as addition and counterclockwise rotation as subtraction, then addition and subtraction in a closed continuous natural number loop can be interchangeable.
2. The effect is the same between 5 and 5 + 12n. That is, as long as the remainder of the two numbers divided by the total number of digits in the loop is the same, the effect is the same.

This law is called congruence in mathematics:

if two integers a and b have the same remainder when divided by an integer m, they are said to be congruent modulo m.

Written as a ≡ b (mod m), a and b are congruent modulo m.

5 mod 12 = 5
17 mod 12 = 5
29 mod 12 = 5

Therefore, 5, 17, and 29 are congruent modulo 12.

4.2 More About Congruence

In order to understand why computers use two’s complement, we need to know that, due to the limited memory length of computers, computer operations are essentially modular arithmetic.

For example, with a 32-bit integer length, a computer can represent 2³² or 4,294,967,296 different states. When we calculate 1 + 2 on a computer, it is essentially a modular arithmetic operation.

 

a ≡ 1 (mod 4294967296)
b ≡ 2 (mod 4294967296)
r ≡ a + b ≡ 3 (mod 4294967296)

Returning to the example of the clock face, let’s write 12 on the clock face as 0. Now our clock face represents 12 numbers from 0 to 11. We take 0 as the starting point and use 12 as the modulus. Turning the clock hand counterclockwise gives us negative numbers, while turning it clockwise gives us positive numbers. For example, if we turn the hand counterclockwise by one position, we get -1. Since -1 and 11 are congruent modulo 12, they are equivalent. By using this property of congruence, we can introduce negative numbers.

Now, let’s consider putting the numbers 0000 0000 to 1111 1111 on a clock face. The pattern is the same as that of the clock face with only 12 positions. For example, 11111111 can represent 255 or -1, and in modular arithmetic, they are equivalent. With 8 bits, we have a total of 256 states. Since we want to introduce negative numbers, we want the same number of positive and negative numbers.

Therefore, we represent 1 to 127 as 0000 0001 to 0111 1111, and -1 to -127 as 11111111 to 10000001, with two additional numbers 0000 0000 and 1000 0000. Naturally, 0000 0000 represents 0. What about 1000 0000? It can represent either 128 or -128, but for consistency and ease of data processing, we use it to represent -128, so that the highest bit of all negative numbers is 1. The binary codes for these negative numbers are called two’s complement.

After all the introduction, let me tell you where -8 came from. It seems like we have deviated from the concept of two’s complement. What is the essence of two’s complement? In fact, two’s complement is just a mathematical rule behind the previous content. We use 1111 1111 to 1000 0000 to represent -1 to -128.

5. How are Integers Stored in Memory ?

Using two’s complement representation, we can handle both positive and negative numbers with a single format.

This simplifies arithmetic operations because addition and subtraction of two’s complement numbers are done in the same way as for unsigned numbers, using only the regular binary addition algorithm  (CPU does not have subtractor )

In addition, converting between two’s complement and unsigned representation can be done with a simple bitwise complement operation, which does not require any additional hardware.

Therefore, using two’s complement representation for storing and processing numbers in computer systems is a very efficient and practical approach.

5.1 CPU Adder

The CPU adder is a key component in computer hardware that is responsible for performing arithmetic operations, specifically addition. It is a combinational logic circuit that receives two input values, adds them together, and produces a single output value.

Modern CPUs typically have multiple adders, each with different bit widths to handle different types of operations. For example, a CPU might have a 32-bit adder for integer addition and a separate 64-bit adder for floating-point addition.

The design of adders is critical for CPU performance, as addition is a common operation in computer programs. As a result, much effort has been put into optimizing adder designs for speed and efficiency, including the use of specialized techniques like carry-lookahead adders and carry-select adders.