Ones' complement

The one's complement, and (B -1) complement, is an arithmetic operation on binary numbers. In this case, all numbers or bits to be inverted, i.e. 0 becomes 1 and vice versa. This is also referred to as a non- arithmetic logic. In the programming languages ​​C, C , C #, Perl, PHP, or Java, this operation is represented by the symbol ~. The one's complement is of particular importance if you want to manipulate individual bits. If you want to, for example, the value delete all the bits that are set up in value, so you must be the one's complement of bitwise and - link.

One application of the one's complement is the one's complement, a method to represent negative numbers in the binary system, without additional symbols such as and - to be instructed. This is especially important for computers whose logic is geared solely to bits, that is, sequences of 0 and 1 's complement of integers pulls in most cases significant problems in the implementation of an arithmetic unit according to, which is why they rarely used will. Low advantages it has only the already mostly slow division and multiplication in extended twice with a long result.

Motivation

As represented by bits in the binary encodings of negative numbers both sign and the actual number, it is important to know which bit is used for what. This is normally achieved by all numbers have a constant number of digits and are filled as needed with leading zeros in the binary system. The one's complement at the first bit of an n- bit data word for the encoding of the sign is used and the n-1 following the code number. This positive numbers, leading zeros, negative contrast leading ones are added.

If one uses the one's complement of encoding numbers as positive numbers will always have a leading 0 to encode the plus. Negative numbers are represented by negation of the complete bit pattern of the corresponding positive number and, therefore, start with a 1 to encode the negative. The first bit is therefore reserved for the sign. It should never be confused with one 's complement of an unsigned binary number; For example, in 1010 represented the first case -5, while in the latter case is meant 10.

The biggest problem of the one's complement ( and also the main difference between the two's related ) is that the number 0 two representations exist: one with negative and one with positive sign. The range of values ​​of the one's complement comprises at n binary digits generally the symmetric region

Examples:

8 Bit: -127 (10 ) to 127 (10 ) at 16 bit: -32767 (10 ) to 32767 (10 ) 32 Bit: -2147483647 (10 ) to 2147483647 (10 ) For 64 bits: -9223372036854775807 (10 ) to 9223372036854775807 (10 ) Arithmetic operations and problems

The examples below use three digits for the coding of the amount and a number for the coding of the sign (the example is thus a 4-bit or 1 - nibble ( half-byte ) representation). Displayable numbers with a word length of 4 bits:

By negation, a case distinction for positive and negative numbers omitted: To -4 3 = -1 represent only the corresponding figures must be added. The addition is done by adding the Einerkomplementdarstellungen as unsigned binary numbers.

Example:

-4 3 = -1 leads to            1011         0011 Carry 0011           -----         = 1110 Disadvantage of the one's complement is the treatment of the case, when during an operation, the zero is passed. Example: When calculating -4 6 = 2 appears after a simple binary number addition of the two Einerkomplementdarstellungen initially an incorrect intermediate result:

-4 6 = 2 leads to            1011         0110 Carry 1110           -----         = 0001 ( interim result) The 0001 would be for 1, 2 for not. Thus, a correct result appears, the leftmost transfer must be evaluated (here 1 ) and, if the result will be increased by 1. In other words, the transfer needs to be added to the intermediate result:

0001 ( interim result)         1 (carry forward the previous operation )           -----         = 0010 In the first example above, the carry is 0, so the intermediate result is already there, the end result.

Another disadvantage is the emergence of a redundancy: there are two representations for zero: 0000 ( 0) and 1111 ( -0 ), see signed zero. On the one hand is not used, the maximum dimension of the amount of numbers representable with a limited number of bits. The number representable space is reduced by 1; since the zero is present twice, falls off a data word for the number space. The presentation of any other number remains unique. In the example here with 4 bits are represented ( -7 to 7 ) with the 24 = 16 different bit combinations 15 different numbers.

Both problems are described in the coding of numbers in the two's complement representation, which is based on the one's complement, is avoided.

For more information

• John Walker: Minus Zero, UNIVAC Memories - one's complement on UNIVAC 1100 computers ( English)