Showing posts with label Arithmetic. Show all posts
Showing posts with label Arithmetic. Show all posts

1's complement and 2's complement

In general, we (human beings) express negative numbers by placing a minus (-) sign at the left end of the number. Similarly while representing the integers in binary format, we can leave the left-most bit be the sign bit. If the left-most bit is a zero, the integer is positive; if it is a one, it is negative.

To make it easy to design computers which do integer arithmetic, integers should obey the following rules:

(1) Zero is positive and -0 = 0
(2) The top-most bit should tell us the sign of the integer.
(3) The negative of a negative integer is the original integer ie., --55 is 55.
(4) x - y should give the same result as x + -y. That is, 8 - 3 should give us the same result as 8 + -3.
(5) Negative and positive numbers shouldn't be treated in different ways when we do multiplication and division with them.

2s complement has become the standard method of storing signed binary integers. It allows the representation of numbers in the range – (2n) to 2n-1, and has the major advantage of only having one encoding for 0.

A simple and elegant way to represent integers which obeys these rules is called 2s complement. The 2s complement of an integer is calculated by changing all bits of integer from 1 to 0 & 0 to 1, then adding 1 to the result.

1's complement addition is distinguished from the 2's complement addition typically encountered in (unsigned) computer arithmetic by how overflow bits are handled. 1's complement overflow bits are carried around back into the sum while 2's complement overflow bits are discarded. In general, the inverse of a number under a given mathematical operation is the value which when operated on with that number returns the identity element. The 1's complement additive inverse of a number is its bitwise complement (replace 0s with 1s and 1s with 0s). This proposal relies on a number and its complement summing to zero (the additive identity element). Actually they sum to negative zero--1's complement addition has two identity elements. Recall that an identity element under a given operation is a value which leaves any other number unchanged when the operation is applied. Under 1's complement arithmetic the addition of either zero (all 0's) or negative zero (all 1's) to a number will generate a sum equal to the original number.

1's complement addition is both associative and commutative (it forms an Abelian group over the unsigned integers), so it is immaterial whether an identity element is added to a number or the number is added to an identity element, or whether the number operates on its inverse or the inverse operates on the number--both arrangements have the same result. Also note that the operation of subtraction is equivalent to adding the inverse (complement) of the number.