Actions

Two's complement

From Sonic Retro

Revision as of 23:47, 10 January 2008 by Aurochs (talk | contribs)

Two's complement is by far the most common method of representing signed numbers (those that can be either negative or positive) in computing. Any positive integer can be changed into a negative integer by taking its two's complement, and vice versa. Any signed number with a 1 in the highest bit position (the most significant bit, or MSB) is considered to be negative in this system.

Two's complement is calculated by taking the bitwise NOT of a number (or complementing it) and adding one to the result. Any carry (overflow) bits are ignored. For instance, to find -7, we would start with the eight-bit binary number 0000 0111:

!(0000 0111) = 1111 1000
1111 1000 + 1 = 1111 1001

The process is reversable:

!(1111 1001) = 0000 0110
0000 0110 + 1 = 0000 0111

Let's say we wanted to find the two's complement of 0.

!(0000 0000) = 1111 1111
1111 1111 + 1 = 1 0000 0000 = 0000 0000

The two's complement of 0 is 0. A negative zero is impossible when using two's complement.

It is very simple and cheap to implement signed addition when using two's complement, because you do not need to determine the sign beforehand. For example, let's take 5 + -3:

  0101
+ 1101
------
 10010 = 0010

The intermediate result is 18, which seems incorrect. But dropping the overflow bit gives us the correct answer of 2. This works for any set of numbers. Note that 5 + (-3) is the same as 5 - 3. It follows that we can use an adder circuit to subtract numbers by taking the two's complement of the subtrahend if the numbers have the same sign.