Integer, Two's complement

This page was translated by a robot.

Integers are represented in a computer using the binary system, i.e. the digits 0 and 1. This system is defined analogously to the decimal system common to humans today, which uses the digits 0 to 9. In the decimal system, a so-called sign is used in addition to the digits to mark a number as positive or negative. In the binary system, however, no additional characters apart from 0 and 1 can occur, which is why signed integers must be stored using a special coding. The coding that is common today stores negative values ​​as a so-called two's complement .

A Javascript program to illustrate the coding of integers can be found at Number System Converter .

Details

unsignedUnsigned integers of a specific bit length are declared with the modifier in C and C++ . They are represented by an ordered enumeration in the binary system and use all available bits to store the numerical value. Since they are defined as unsigned, they are always positive. A detailed discussion can be found on the number systems page . At this point, the following examples for unsigned integers with 16 bits should suffice for illustration:

Binary
0000 0000 0000 0000
0000 0000 0000 0001
0000 0000 0000 0010
0000 0000 0000 0011
0000 0000 0000 0100
...

Decimal
0
1
2
3
4
...

In addition to unsigned integers, there are also signed integers, i.e. numbers that are explicitly marked as either positive or negative. In C and C++, signed integers are declared with the signedmodifier . However, since a processor basically does not work with values ​​but with data, it cannot distinguish whether the data is signed or unsigned integers.

1101 1001 1001 1101
1101 1001 1001 1101

55709  unsigned
-9827  signed

An integer is specially encoded so that a processor can calculate quickly and easily with both unsigned and signed numbers

Encoding of Signed Integers

The goal of coding for signed integers is to shift the value range of the number in such a way that both positive and negative values ​​can be mapped, but the behavior of the bit operations required for arithmetic calculations in the processor does not change.

The most significant bit of a signed integer is interpreted as the sign. If the bit is set to 0, the number has a positive sign and if the bit is set to 1, the number has a negative sign. This bit is also referred to as the sign bit. All remaining bits store the actual numerical value.

Positive signed integers are encoded in exactly the same way as unsigned integers, but the range of values ​​is limited so that the sign bit is not changed. The number 0 serves as the basis, which is encoded in binary with nothing but zeros.

0000 0000 0000 0000
0000 0000 0000 0001
0000 0000 0000 0010
...
0111 1111 1111 1101
0111 1111 1111 1110
0111 1111 1111 1111

0
1
2
...
32765
32766
32767

As long as a positive integer does not exceed the value range, it is irrelevant whether the number is signed or unsigned, since it is encoded exactly the same.

The coding of negative integers follows from the consideration of what happens when the number 0 is subtracted from the number 1. In the case of unsigned integers, the value range is undershot (underflow) and a so-called wrap-around takes place, i.e. all bits change from all zeros to all ones. Precisely this encoding is defined as the number -1 for signed integers. If the subtraction is continued with 1, all other negative numbers are found.

0000 0000 0000 0000
1111 1111 1111 1111
1111 1111 1111 1110
1111 1111 1111 1101
...
0
-1
-2
-3
...

The range of values ​​for negative numbers is limited so that the sign bit is not changed. This results in the following coding table as an example for signed integers with 16 bits:

0111 1111 1111 1111
0111 1111 1111 1110
...
0000 0000 0000 0010
0000 0000 0000 0001
0000 0000 0000 0000
1111 1111 1111 1111
1111 1111 1111 1110
...
1000 0000 0000 0001
1000 0000 0000 0000

32767
32766
...
2
1
0
-1
-2
...
-32767
-32768

Two's complement

The term two's complement refers to the conversion from a positive number to its corresponding negative counterpart, e.g. the conversion from 42 to -42. The two's complement is also referred to as 2 's complement . The name comes from the idea that a positive n-bit number can be converted to its negative counterpart by subtracting the number from the power of two2^n :

Two's complement =
(2 ^ n) - number

However, the value 2^ncannot be stored in an n-bit integer. Therefore, 1 is subtracted from this value and then 1 is added again:

Two's complement =
(2 ^ n) - 1 - number + 1

The value (2^n)-1corresponds to an unsigned integer with n bits, which has all binary ones. However, when this value is interpreted as a signed integer, it is equivalent to -1:

1111 1111 1111 1111
1111 1111 1111 1111

(2 ^ n) - 1
-1

Plugging this interpretation into the two's complement formula gives the mathematical sense of a negative number.

Two's complement =
Negative number  =
Negative number  =

(2 ^ n) - 1 - number + 1
         -1 - number + 1
            - number

Based on these considerations, the following example can be easily understood:

    1111 1111 1111 1111
-   0110 0100 1101 0100
    -------------------
    1001 1011 0010 1011
+   0000 0000 0000 0001
    -------------------
    1001 1011 0010 1100

      -1
-  25812
--------
  -25813
+      1
--------
  -25812

It should be noted that this conversion works the same way when converting a negative number back to its positive counterpart:

    1111 1111 1111 1111
-   1001 1011 0010 1100
    -------------------
    0110 0100 1101 0011
+   0000 0000 0000 0001
    -------------------
    0110 0100 1101 0100

      -1
- -25812
--------
   25811
+      1
--------
   25812

In C and C++, the negative operator performs this conversion on integers. It should be noted that due to the definition of the two's complement there are two values ​​for each integer type, which remain unchanged by the negative operator. These are the value 0(zero) and the minimum possible value of the integer type.






0
-128
#include <stdio.h>

int main(){
  signed char a = 0;
  signed char b = -128;
  printf("%hhd\n", -a);
  printf("%hhd\n", -b);
  return 0;
}

One's Complement

If you carefully study the two's complement examples shown above, you will notice that subtracting the number from -1 simply reverses the bits, i.e. every 0 becomes a 1 and vice versa. This is the same as concatenating the number with the bitwise NOT operator .

    1111 1111 1111 1111
-   0110 0100 1101 0100
    -------------------
    1001 1011 0010 1011


~   0110 0100 1101 0100
    -------------------
    1001 1011 0010 1011

This conversion is called the so-called one's complement . The name derives from the fact that the number is subtracted from all ones .

Thus, the one's and the two's complement can be written and linked as follows:

One's complement =
One's complement =

Two's complement =
Two's complement =
(2 ^ n) - 1 - number
            ~ number

(2 ^ n) - 1 - number + 1
    One's complement + 1

On certain systems, the one's complement is used to encode negative numbers. Say: A number encoded in one's complement is positive if the sign bit 0is and negative if the sign bit 1is . If the number is negative, its absolute value is defined by the one's complement of the bit sequence.

The one's complement as coding for negative integers has the disadvantage that negative and positive value ranges do not merge smoothly when adding and subtracting. For example, if the number 1 is subtracted from the number 0(zero), the result is the bit sequence in an 8-bit integer, for example 11111111, which corresponds to the value -0.

Sign and Magnitude

For the sake of completeness, a third encoding of negative integers will be discussed very briefly: Sign and Magnitude . This encoding uses one bit to store the sign, just like the one's and two's complement, but interprets the remaining bits simply as a positive integer.

This coding is also occasionally used on certain systems, but has the same disadvantages as the one's complement and also means that, depending on the operation, a distinction must be made as to whether the sign bit is set or not. Say: For example, an addition on negative numbers must be treated differently than on positive numbers.

Integers in C and C++

In modern systems, it can be assumed that negative numbers are encoded using two's complement.

The bit size of the number can be specified using the types defined in the stdintlibrarychar , or in the traditional way using the , short, int, longand types long long. However, these have a different number of bits depending on the system. Corresponding macros for determining the bit sizes used on a system are defined in the limitslibrary .

It should be noted that C and C++ set the corresponding assembler commands according to the declared type. As a result, there is no special handling for overflow or underflow, just like in assembler. Accordingly, wrap-arounds can occur and also conversions between signedand unsignedcan result in misinterpretations of the sign bit. Further information on this can be found under the respective types, as well as under arithmetic conversion .

An example of special handling of signed integers can be found in the shift-right operator . For more information on the various arithmetic operations involving integers, see the Integer Arithmetic page and the Number System Converter example program .

Next Chapter: Real Number, Floating Point