Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "C++ original code, inverse code, complement example analysis". The editor shows you the operation process through an actual case. The operation method is simple, fast and practical. I hope this article "C++ original code, inverse code, complement example analysis" can help you solve the problem.

First, the number of machines and true value

Before learning the original code, inverse code and complement code, you need to understand the concept of machine number and true value.

1. Number of machines

A binary representation of a number in a computer, called the machine number of this number. The machine number is signed, and the symbol is stored in the highest bit of a number in the computer, with a positive number of 0 and a negative number of 1.

For example, the number + 3 in the decimal system, the computer word length is 8 bits, and the conversion to binary is 00000011. If it's-3, it's 10000011.

So, 00000011 and 10000011 here are the number of machines.

2. True value

Because the first bit is a symbolic bit, the formal value of the machine number is not equal to the real value. For example, the signed number above is 10000011, the highest bit 1 is negative, and its real value is-3 instead of the formal value 10000011 (131converted to decimal equals 131). Therefore, for the sake of difference, the real value corresponding to the number of machines with symbols is called the true value of the number of machines.

Example: true value of 0000 0001 = + 0001 0001 = + 1 0001 0001 =-1

Second, the basic concepts and calculation methods of original code, inverse code and complement code.

Before exploring why machines use complements, let's understand the concepts of source code, inverse code and complement. For a number, the computer should use a certain coding method to store. The original code, inverse code, and complement code are the coding methods in which a machine stores a specific number.

1. Original code

The original code is the symbol bit plus the absolute value of the true value, that is, the first bit represents the symbol and the remaining bits represent the value. For example, if it is an 8-bit binary:

[+ 1] original = 0000 0001

[- 1] original = 1000 0001

The first place is the symbol bit. Because the first bit is a symbolic bit, the range of values for 8-bit binary numbers is:

[1111 1111, 0111 1111]

That is,

[- 127127]

The original code is the easiest way for the human brain to understand and calculate.

2. Inverse code

The representation of the inverse code is:

The inverse of a positive number is itself.

The inverse code of a negative number is based on its original code, the symbol bits remain unchanged, and the other bits are inverted.

[+ 1] = [00000001] original = [00000001] inverse

[- 1] = [10000001] original = [11111110] inverse

It can be seen that if an inverse code represents a negative number, the human brain cannot directly see its value. It is usually converted to the original code and then calculated.

3. Complement

The representation of the complement is:

The complement of a positive number is itself.

The complement of a negative number is based on its original code, the symbol bit is unchanged, the rest of you are reversed, and finally + 1. (that is, + 1 on the basis of inverse code)

[+ 1] = [00000001] original = [00000001] inverse = [00000001] complement

[- 1] = [10000001] original = [11111110] inverse = [11111111] complement

For negative numbers, the complement representation is also impossible for the human brain to directly see its value. Usually it also needs to be converted to the original code before calculating its value.

Third, why use the original code, inverse code and complement code

Before starting in-depth study, my advice is to "memorize" the original code, the representation of inverse code and complement code, and the method of calculation.

Now we know that a computer can encode a number in three ways. For positive numbers, because the results of all three encodings are the same:

[+ 1] = [00000001] original = [00000001] inverse = [00000001] complement

So there is no need for too much explanation. But for negative numbers:

[- 1] = [10000001] original = [11111110] inverse = [11111111] complement

It can be seen that the original code, inverse code and complement code are completely different. Since the original code is directly recognized by the human brain and used to calculate the representation, why are there inverse codes and complement codes?

First of all, because the human brain can know that the first bit is the symbol bit, we will choose to add and subtract the truth region according to the symbol bit. The concept of truth value is at the beginning of this article. But for computers, addition and subtraction multipliers are already the most basic operation, and the design should be as simple as possible. It is obvious that computer recognition of "symbol bits" will make the basic circuit design of the computer very complicated! So people came up with a way to involve symbolic bits in the operation. We know that subtracting a positive number according to the algorithm is equal to adding a negative number, that is, 1-1 = 1 + (- 1) = 0, so the machine can only add but not subtract, so the design of computer operation is easier.

So people began to explore the way to participate in the operation of symbol bits and keep only addition. First of all, let's look at the original code:

The expression for calculating the decimal system: 1-1: 0

1-1 = 1 + (- 1) = [00000001] original + [10000001] original = [10000010] original =-2

If it is expressed in the original code and the symbol bits are also involved in the calculation, it is obvious that the result is incorrect for subtraction. This is why the original code is not used inside the computer to represent a number.

In order to solve the problem of subtraction of the original code, there is an inverse code:

The expression for calculating the decimal system: 1-1: 0

1-1 = 1 + (- 1) = [0000 0001] original + [1000 0001] original = [0000 0001] anti + [1111 1110] inverse = [1111 1111] inverse = [1000000] original =-0

It is found that the true value of the result is correct when the inverse code is used to calculate the subtraction. The only problem is actually the special value of "0". Although people understand that + 0 and-0 are the same, 0 sign does not make any sense. And there will be two codes [0000 0000] and [1000 0000] that represent 0.

As a result, the emergence of the complement solves the problem of the symbol of 0 and two coding:

1-1 = 1 + (- 1) = [0000 0001] original + [1000 0001] original = [0000 0001] complement + [1111 1111] complement = [0000 0000] complement = [0000000] original

So 0 is expressed as [0000 0000], but the previously problematic-0 no longer exists. And it can be expressed as [1000 0000]:

(- 1) + (- 277) = [1000 0001] original + [1111 1111] original = [1111 1111] complement + [1000 0001] complement = [1000 0000] complement

The result of 1-127should be-128. in the result of complement operation, [1000 0000] complement is-128. Note, however, that because the previous-0 complement is actually used to represent-128,-128 has no original and inverse representation. (the complement of-128indicates that the original code calculated by [1000 0000] is [0000 0000], which is incorrect.)

The use of complement not only fixes the symbol of 0 and the problem of two encodings, but also represents a minimum number. This is why the range of 8-bit binary is [- 127, + 127] in source or inverse code, and [- 128,127] in complement.

Because the machine uses complement, for the 32-bit int type commonly used in programming, the range is: [- 231,231-1] because the first bit represents the symbol bit. When using complement representation, you can save one more minimum value.

Fourth, the original code, the inverse code, and the complement code go deeper.

The computer skillfully participates in the operation of symbolic bits and turns subtraction into addition. what kind of mathematical principles are contained behind it?

Think of a clock as a 1-digit decimal number. If the current time is 6 o'clock and I want to set the time to 4 o'clock, what do I need to do? We can:

1. Dial back 2 hours: 6-2 = 4

two。 Dial forward 10 hours: (6 + 10) mod 12 = 4

3. Dial forward 10-12-22 hours: (6-22) mod 12 = 4

(2) the mod in the mod 3 method refers to the module operation, 16 mod 12 = 4, that is, the remainder after dividing 16 by 12 is 4.

So the result of clock dial back (subtraction) can be replaced by forward dial (addition)!

Now the focus is on how to replace a negative number with a positive number. We can feel some clues and find some rules in the above example. But mathematics is rigorous. You can't rely on feeling.

First of all, a related concept in mathematics: congruence

The concept of congruence

Two integers a _ () _ (b) are said to be congruence with respect to module m if the remainder of their division by m is equal.

Write down as a ≡ b (mod m)

Read as an and b with respect to module m congruence.

Examples are as follows:

4 mod 12 = 4

16 mod 12 = 4

28 mod 12 = 4

So 4, 16, 28 on module 12 congruence.

Negative number modulus

It is very simple for positive numbers to perform mod operations. But what about negative numbers?

The following is a mathematical definition of mod operations:

The screenshot above, the "unbound" symbol can not find how to enter (garbled after being pasted in word). The following is the "unbound" symbol that replaces the above figure with "L" and "J":

X mod y = x-y L x / YJ

The above formula means:

X mod y equals x minus y times the lower bound of the quotient of x and y.

Take-3 mod 2 as an example:

-3 mod 2

=-3-2xL-3Comp2J

=-3-2xL-1.5J

=-3-2x (- 2)

=-3 + 4 = 1

So:

(- 2) mod 12 = 12-2x10

(- 4) mod 12 = 12-4 = 8

(- 5) mod 12 = 12-5 = 7

Start to prove

Back to the question of clocks:

Call back 2 hours = dial forward 10 hours

Call back 4 hours = dial forward 8 hours

Call back 5 hours = dial forward 7 hours

Pay attention to the pattern found here!

Combined with the concept of congruence learned above. In fact:

(- 2) mod 12 = 10

10 mod 12 = 10

-2 and 10 are congruent.

(- 4) mod 12 = 8

8 mod 12 = 8

-4 and 8 are congruent.

It is getting closer and closer to success. In order to replace negative numbers with positive numbers, we only need to apply two theorems of congruence numbers:

Reflexivity:

A ≡ a (mod m)

This theorem is very obvious.

Linear operation theorem:

If a ≡ b (mod m), c ≡ d (mod m) then:

(1) a ±c ≡ b ±d (mod m)

(2) a * c ≡ b * d (mod m)

If you want to see the proof of this theorem, please see: http://baike.baidu.com/view/79282.htm

So:

7 ≡ 7 (mod 12)

(- 2) ≡ 10 (mod 12)

7-2 ≡ 7 + 10 (mod 12)

Now we find its positive congruence for a negative number. But it is not 7-2 = 7-10, but 7-2 ≡ 7-10 (mod 12), that is, the remainder of the calculated result is equal.

Let's go back to the binary problem and take a look at the 2-1-1 problem.

2-1 2 + (- 1) = [0000 0010] original + [1000 0001] original = [0000 0010] anti + [1111 1110] inverse

At this point, the inverse of-1 is 1111 1110. If [1111 1110] is regarded as the original code here, then [1111 1110] originally =-126. if the symbol bit is removed here, it is considered to be 126.

It is found that there are the following rules:

(- 1) mod 127126

126 mod 127 = 126

That is:

(- 1) ≡ 126( mod 127)

2-1 ≡ 2x126 (mod 127)

The result of the remainder of 2-1 and 2-126 is the same! And this remainder is the result of our expected calculation: 2-1-1.

So the inverse code of a number is actually the congruence of this number to a membrane. And this membrane is not our binary system, but the maximum value that can be expressed! This is like a clock, after turning around, you can always find a correct value within the expressible range!

The 2th 126 is obviously equivalent to a turn of the clock, and because the symbol bit is involved in the calculation, it happens to form the correct result with the highest bit of the overflow.

Since inverse codes can turn subtraction into addition, what about the complements used by computers now? Why can you get the correct result by adding 1 to the inverse code?

2-1 2 + (- 1) = [0000 0010] original + [1000 0001] original = [0000 0010] complement + [1111 1111] complement

If you take [1111 1111] as the original code and remove the symbol bits, then:

[0111 1111] originally = 127,

In fact, + 1 on the basis of inverse code is only equivalent to increasing the value of the membrane:

(- 1) mod 128 = 127

127128128 = 127For mod

2-1 ≡ 2x127( mod 128)

At this point, the dial is equivalent to one round for every 128 scales. Therefore, the minimum and maximum values of the operation results represented by complement should be [- 128,128].

However, due to the special case of 0, there is no way to represent 128, so the value range of the complement is [- 128,127].

This is the end of the content of "C++ original code, inverse code, complement example analysis". Thank you for your reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.