The article directories

    • A, quotes
    • Number of machines and truth value
      • 1. Number of machines
      • 2, the true value
    • Computer coding
      • 1, the original code
      • 2, complement
      • 3, radix-minus-one complement
      • 4. Coding summary
    • Four, why to use complement code
      • 1. Main purpose
      • 2. Source code operation
      • 3. Inverse code operation
      • 4. Complement operation
    • 5. Back to square one

A, quotes

	printf("%d\n".abs(INT_MIN));
Copy the code
  • What should the correct output of this code be?
  • It must be a positive number intuitively, because abs is a function that takes the absolute value of a number, and mathematically the absolute value of any number is greater than or equal to zero; However…

– 2147483648.

  • So let’s look at what’s going on behind the computer;

Number of machines and truth value

1. Number of machines

  • We know that the computer is composed of 1 s and 0 s internal code, either an integer or floating point, involve negative, for machine is don’t know the positive and negative, while the “positive” and “negative” exactly two opposing state, so the rules with “0” said “is”, “negative”, “1” said such symbols will be digitized, And if you put it in front of a significant number, it becomes a signed number;
  • The number marked “digital” is called machine number;

2, the true value

  • Numbers with “+” or “-” are called truth values;
  • However, once the sign bit and the numeric part are put together, how do you get them to participate in the operation together? And that’s where all the coding comes in;

Computer coding

1, the original code

  • The source code here does not mean source code (source code), but the simplest representation of the number of machines; For the sake of quick comprehension, I will only introduce integers, not decimals;

[Original code definition] Sign bit 0 represents positive number, sign bit 1 represents negative number, value bit is the absolute value of true value.

[x] the original (0 < = = {x x < 2 n – 1) (2 n – 1 – x – 2 n – 1 < < x = 0) _ the original = \ [x] begin {cases} x & (0 < = x < 2 ^ \ \ {}, n – 1) 2 ^ {}, n – 1 – x & (2 ^ {}, n – 1 < < = 0) in x \ \ \ end original = {{cases} [x] x2n – 1 – x (0 < = x < 2 n – 1) (n – 2-1 < < x = 0) (here n n n value is 8, 16, 32, 64 8, 16, 32, 64 8, 16, 32, 64 8, 16, 32, 64 8, 16, 32, 64 8, 16, 32, 64 8, 16, 32, 64 8, 16, 32, 64

【 Source code example 】

  • 1) True value x = +100101, the source code is: 00100101;
  • 2) true value x = -100101, source code: 10100101;
  • Is the most close to human’s original code, and easily transformed and true value, but lets the computer with the original codes of addition and subtraction is too cumbersome, if two Numbers the sign bit is different, need to determine the absolute value size, and then use the absolute value of minus the absolute value is small, the absolute value of number shall prevail and symbols, is originally addition is needed to use subtraction to implement; In order to make the computer do things as simple as possible, so the design of the complement code;

2, complement

The complement of a positive number is itself, and the sign bit is 0. The complement of negative numbers is +1 after the value bit of the original code is reversed, and the sign bit is 1. [x] fill = {x (0 < = x < 2 n – 1) (2 n + x – 2 n – 1 < = x < 0) _ fill = \ [x] begin {cases} x & (0 < = x < 2 ^ {}, n – 1) \ \ 2 ^ {n} + x & (2 ^ {}, n – 1 < = x < 0) \ \ \ end {cases} [x] fill = {x2n + x (0 < = x < 2 n (n – 1-2-1) < = x < 0) [complement for example]

  • 1) When true value x = +100101, complement code is: 00100101;
  • 2) When the true value x = -100101, the complement code is 11011011;

(Try adding the numeric part of a negative number to its complement to get 2n 2^n 2n.)

3, radix-minus-one complement

  • The inverse code is usually used as the intermediate transition of complementary code or complementary code.

The inverse of an integer is itself, the sign bit is 0; The inverse code of negative numbers is the value of the original code, and the sign bit is 1. [x] anti = {x (0 < = x < 2 n – 1) (2 n – 1 + x – 2 n – 1 < < x = 0) _ anti = \ [x] begin {cases} x & (0 < = x < 2 ^ \ \ {}, n – 1) ^ 2 + x {n} – 1 & 2 ^ (- {}, n – 1 < < = 0) in x \ \ \ end {cases} [x] anti = {x2n – 1 + x (0 < = x < 2 n – 1) (n – 2-1 < < x = 0) [radix-minus-one complement for example]

  • 1) When true value x = +100101, complement code is: 00100101;
  • 2) When the true value x = -100101, the complement code is 11011010;

(Try adding the numeric part of a negative number to its complement to get 2n−1 2^n-1 2n−1)

4. Coding summary

  • 1) The highest bits of these three machine numbers are all sign bits;
  • 2) When the true value is positive, the representation form of source code, complement code and inverse code is the same, the symbol bit is represented by “0”, and the truth value of numeric part is the same;

[+1] = [00000001] Original = [00000001] Inverse = [00000001] Complement [+1] = [00000001]_ Original = [00000001]_ Inverse = [00000001]_ Complement [+1]=[00000001] Original =[00000001] Inverse =[00000001] Complement

  • 3) When the true value is negative, the representation forms of source code, complement code and inverse code are different, but the symbol bits are all represented by “1”, and the numerical part: the inverse code is the “inversion of each” of the original code, and the complement is the “inversion plus 1” of the original code;

[− 1] = [10000001] Original = [11111110] Inverse = [11111111] Complement [-1] = [10000001] Original = [11111110] Inverse = [11111111] Complement [−1]=[10000001] Original =[11111110] Inverse =[11111111] Complement

Four, why to use complement code

1. Main purpose

  • The four operations of the computer are designed to be as simple as possible. But the introduction of the concept of sign bit, for the computer to consider the addition of positive and negative numbers, is equal to the introduction of subtraction, so the hope is that the bottom of the computer design only an adder, can add and subtraction are done.

2. Source code operation

  • For source code addition, two positive numbers add as follows:

1 + 1 = [00000001] Original + [00000001] Original = [00000010] Original 1 + 1 = [00000001]_ Original + [00000001]_ Original = [00000010]_ Original 1+1=[00000001] Original +[00000001] Original =[00000010] Original = 2

  • There seems to be no problem? So people began to explore subtraction, but the original intention of the designers was to include both addition and subtraction without subtraction, so we tried to use the negative representation of the original code to do the operation;

1 − 2 = 1 + (− 2) = [00000001] Original + [10000010] Original = [10000011] Original 1-2 = 1 + (-2) = [00000001]_ Original + [10000010]_ Original = [10000011] _ the original 1-2 = 1 + (2 -) = [00000001] the original + [10000010] the original = [10000011] = 3

  • This result is wrong, so in order to solve the problem of subtraction, inverse code operation is introduced;

3. Inverse code operation

  • For the addition of inverse codes, one plus one minus two numbers add as follows:

1 − 2 = 1 + (− 2) = [00000001] Inverse + [11111101] Inverse = [11111110] Inverse 1-2 = 1 + (-2) = [00000001]_ inverse + [11111101]_ inverse = [11111110] _ the 1-2 = 1 + (2 -) = [00000001] against the + [11111101] and [11111110] = = 1

  • No problem? But in some cases, the inverse code can be ambiguous, when two identical numbers are subtracted, as follows:

1 − 1 = 1 + (− 1) = [00000001] Inverse + [11111110] Inverse = [11111111] Inverse 1-1 = 1 + (-1) = [00000001]_ inverse + [11111110]_ inverse = [11111111] _ anti – 1 = 1 + 1 = (1 -) [00000001] against the + [11111110] and [11111111] = = 0

  • Here a strange concept appears, is “negative zero”, the inverse code operation will appear in two codes to represent the value of zero;
  • In order to solve the problem of positive and negative zero, the concept of complement is introduced.

4. Complement operation

  • 1) The sum of two numbers, plus one minus two numbers, and non-zero:

1 − 2 = 1 + (− 2) = [00000001] Complement + [11111110] Complement = [11111111] Complement 1-2 = 1 + (-2) = [00000001]_ complement + [11111110]_ Complement = [11111111] _ for 1-2 = 1 + (2 -) = [00000001] + [11111110] = [11111111] tonic = 1

  • 2) The sum of two numbers, and the answer is zero:

1 − 1 = 1 + (− 1) = [00000001] Complement + [11111111] Complement = [00000000] Complement 1-1 = 1 + (-1) = [00000001]_ complement + [11111111]_ Complement = [00000000] _ fill 1-1 = 1 + (1 -) = [00000001] + [11111111] = [00000000] tonic = 0

When you add two negatives of each other, you get a complement of 2n 2 to the n 2n, which you can say is overflowed, which is the same definition as before;

  • To sum up, the inside of the computer is represented by complement;

5. Back to square one

  • Finally, let me answer the question that I asked at the beginning of the article, why is the absolute value of a negative number still a negative number;

  • This negative number is not an ordinary negative number; it is the minimum of a 32-bit signed integer, i.e. : INT_MIN=−231 INT\_MIN = -2^{31} INT_MIN=−231

  • Its complement is expressed as: [− 2 31] Supplement = [10000000 00000000 00000000 00000000] Supplement [-2^{31}]_ Supplement = [10000000\ \ 00000000\ \ 00000000\ \ 00000000]_ Supplement [−231] Supplement =[10000000 00000000 00000000 00000000] Supplement

  • Starting from the definition of complement: [x] fill = {x (0 < = x < 32 + x (31) 2-31 < = 2 x < 0) _ fill = \ [x] begin {cases} x & (0 < = x < 2 ^ {31}) \ \ 2 ^ {32} + x &(-2^{31} <= x < 0)\\ \end{cases} [x] ={

    X232 + x (0 < < = x (231-231) < = x < 0)

31-2 = 2 + 31 31 (31) – 2 = X + fill [31] – 2 = 0 2 ^ {31} – 2 ^ 2 ^ {31} = {31} + (2 ^ {31}) = X + / – 2 ^ {31}] _ = 0 + (231-231 = 231-231) = X + / – 231] = 0

Solving this simple equation yields the unique value of X X X: [10000000 00000000 00000000] Supplement [10000000\ \ 00000000\ \ 00000000\ \ 00000000]_ Supplement [10000000 00000000 00000000 00000000 00000000] to fill

  • So in the system of 32-bit signed integers, INT_MIN=−INT_MIN INT\_MIN = -int \_MIN INT_MIN=−INT_MIN;