What is binary 9s complement

Community

On the start page we looked at the four digits of the value 1337 in the decimal number system.

Now we transfer 1337 times into the binary number system. A quick calculation tells us that one thousand three hundred thirty-seven in binary is 10100111001.

1 * 2 ^ 10 = 1 * 1024 = 1024 0 * 2 ^ 9 = 0 * 512 = 0 1 * 2 ^ 8 = 1 * 256 = 256 0 * 2 ^ 7 = 0 * 128 = 0 0 * 2 ^ 6 = 0 * 64 = 0 1 * 2 ^ 5 = 1 * 32 = 32 1 * 2 ^ 4 = 1 * 16 = 16 1 * 2 ^ 3 = 1 * 8 = 8 0 * 2 ^ 2 = 0 * 4 = 0 0 * 2 ^ 1 = 0 * 2 = 0 1 * 2 ^ 0 = 1 * 1 = 1 ---------------------------- 10100111001 (binary) = 1337 (decimal)

Like the decimal, the binary number begins with the most significant digit on the left. The 11th digit in the binary corresponds to 2 ^ 10, i.e. the value 1024, the fourth digit in the decimal 10 ^ 3, i.e. the value 1000. If you add the values ​​of the individual digits, you get the total value of the number - regardless of the number system.

The whole thing looks similar in the computer. The number is called "the bit" (short for "Binary digit“, In German: binary digit). If the bit is set to 1, you say “The bit is set”, and if the bit is set to 0, you say “The bit is not set” (“The bit is cleared ").
Aside from naming, there is another important feature of computers: Numbers in computers have a limited size.
The reason for this is that computers do not have an infinite amount of space to store numbers and because arithmetic operations for variables with fixed sizes are much easier to implement. 1)

What does this mean for us?

First, it means that from now on we will write binary numbers with all leading zeros, so like this:

00001100 (twelve)

to symbolize that the higher bits of the variable are "there" but not set. 2)

It also means that our range of values ​​no longer goes into infinity. On paper, we can always add more ones and zeros and the number can be as large as we want and accordingly use more space on the paper (larger representation). As already mentioned, the computer does not have unlimited space on its "paper". That is why clearly defined limits are imposed on the range of values. Let's say we take a number with the value two hundred and fifty-three (decimal 253) and have 8 bits of space to represent the number. The binary representation for this number looks like this:

11111101

If this number were on paper, we could add 3 without any problems, and the result would just get one more digit:

100000000

But since we assumed that we only have space for 8 bits, we lose the highest bit again. The result is “00000000” so simply zero. As you have seen, what is quite a high number suddenly becomes a small one. This process is called "overflow" or "overflow".

When an overflow occurs depends on the size of the variable. In our example it was 8 bits, so the highest number is 28 -1. We subtract 1 because we are including 0. For 8 bits this is the decimal number range from 0 to 255.

In today's common PC systems, variable sizes are usually measured in bytes. A byte has (usually) 8 bits, one also speaks of an "octet". In C, the data type “char” is to be equated with a byte. A common “int”, or pointer, has 4 bytes, which means 32 bits. With 32 bits, an unsigned “int” has a value range from 0 to 4,294,967,295 (decimal).

CPUs, on the other hand, are usually specified in bit widths. Modern computers usually have a register width of 32 or 64 bits. A 32-bit CPU can count up to a maximum of 4,294,967,295. If you were to add one, you would get an overflow again and the result is 0.

On paper you can represent negative numbers in the same way as you represent decimal numbers by putting a minus in front of them:
- 1210 = - 11002

A first attempt - the sign

To represent negative numbers in the computer, one could do something similar: we write off a bit of the existing number and assign the meaning of the sign to it. If it is set then the number should be negative and if it is not set then the number should be positive. In our example (and in today's computers) we will use the MSB 3) use
So - 2310 = 1001 0111

We must not forget that we now have one bit less space to display the amount, i.e. 7 in our example. This would give us a value range of 27 -1 = 127.

The problem with this type of representation is that until now only we know what the highest bit means. In order to teach the computer to add correctly, one would first have to query the bit and then toggle between adding and subtracting depending on the status of the bit - this is far too complicated to be effective.

The second attempt - the one's complement

To simplify the calculation with negative numbers, one can use the one's complement: If a number is to be negated, all bits of the number are simply reversed. Example:

from 1710 = 0001 00012 becomes -1710 = 1110 11102

If you reserve the highest bit for the sign, the one's complement fits well with our experiment above: if a number is positive, the highest bit is not set. If the number is negated, the highest bit also changes, and the number is therefore negative.

There are 2 problems:

  • The number 0 now has two display options: 0000 0000 (+0) and 1111 1111 (-0).
  • The addition is still not that easy: you have to add the two numbers, and if there is a carry (carry over, remainder) with the last digit, this has to be added to the first digit. Small example:

17 + (-8) = 9

0001 0001 (17) + 1111 0111 (-8) ------------------- --> 1 0000 1000 +1 <-- ------------------- 0000 1001 ( 9)

The one that “survives” the first addition must be appended to the end so that you get the correct result.

With a number of 8 bits, the one's complement has a value range of - (27-1) = -127 to + (27-1) = 127.

The third attempt - the two's complement

The so-called "two's complement", which is actually used in modern computers, offers a better way of displaying negative numbers.

The two's complement of a number is formed by first taking the one's complement of the number and then adding 1.

2710 = 000110112
-2710 = 111001002 + 1 = 111001012

The properties of this representation are surprisingly very advantageous: If you negate a number twice, the original number comes out again, exactly as it should be:

2710 * (-1) = 000110112 = 111001002 + 1 = 111001012 = -2710
-2710 * (-1) = 111001012 * (-1) = 000110102 + 1 = 2710

The addition of numbers in two's complement representation works by a simple addition, without having to add the rest again:

0001 0001 (17) + 1111 1000 (-8) ------------------- (!) 1 0000 1001 ( 9)

The callsign should indicate that the "carry" must be ignored. If you do that, you will get 0000 10012what 910 which is the correct result.

The value range of the two's complement for a number with 8 digits is -27 = -128 to 27-1 = 127.


This was just a brief introduction to computer binary representation. For a more detailed description, I can refer to chapter 2.1.1 of the eBook "PC Assembly Language" by Dr. Recommend Paul Carter. It can be found here: http://www.drpaulcarter.com/pcasm/

If you like something more precise and mathematical, you should take a look at this website: http://www.cs.uaf.edu/~cs301/notes/Chapter4/node2.html There you will find (with a little brainpower) also pretty detailed things about the binary system.


Author discussion