Signed integers and binary arithmetic

AS · 11 min

Computers must store negative numbers as well as positive ones, and they must add and subtract them using nothing but bits. This note covers one's complement and two's complement representation, binary addition and subtraction, and overflow. Expect a Paper 1 question that asks you to convert a negative denary number to two's complement, add two binary numbers, and say whether the result is valid; the same ideas come back in the A Level floating-point topic.

Unsigned binary

An unsigned binary integer has no sign: every bit is worth a positive amount, so 8 bits store 0 to 255. Unsigned integers are fine for counts, addresses and pixel values, but cannot store $-5$ . To store negative numbers, one bit pattern in every pair has to mean a negative value. There are several ways of choosing which; the syllabus asks for two.

One's complement

In one's complement, a positive number is written in ordinary binary with a leading 0. To make the negative of a number, invert every bit (change each 0 to 1 and each 1 to 0).

$+45 = 00101101$ , so in one's complement $-45 = 11010010$ .

The most significant bit (MSB) therefore acts as a sign bit: 0 for positive, 1 for negative. To read a negative one's complement number, invert it back and put a minus sign in front.

One's complement has a flaw: it has two zeros. 00000000 is $+0$ and 11111111 (the inverse of zero) is $-0$ . This wastes a pattern and makes arithmetic hardware more complicated, because the circuit has to treat two different patterns as equal. The 8-bit range is $-127$ to $+127$ .

Two's complement

Two's complement fixes both problems and is what almost every processor uses. The idea is simple: the most significant bit is given a negative place value.

$-128$	64	32	16	8	4	2	1
1	1	0	1	0	0	1	1

$-128 + 64 + 16 + 2 + 1 = -45$ .

Because only the MSB is negative, a number with MSB 0 is positive and a number with MSB 1 is negative. There is only one zero (00000000), and the range is lopsided by one: $-128$ (10000000) to $+127$ (01111111).

Key result

In $n$ -bit two's complement the MSB has place value $-2^{n-1}$ and the range is

-2^{n-1} \ \text{to}\ 2^{n-1} - 1

Bits	Range
4	$-8$ to $+7$
8	$-128$ to $+127$
16	$-32\ 768$ to $+32\ 767$

In $n$ -bit one's complement the range is $-(2^{n-1} - 1)$ to $2^{n-1} - 1$ , with two representations of zero.

Converting a negative denary number to two's complement

Invert and add one

Write the positive version of the number in binary using the full number of bits.
Invert every bit (this is the one's complement).
Add 1.
Check by adding the place values with the MSB as $-128$ .

A quicker equivalent: starting from the right of the positive number, copy every bit up to and including the first 1, then invert every bit to the left of it. For $+44 = 00101100$ , copy 100, invert 00101 to 11010, giving 11010100 $= -44$ .

A third method uses the negative place value directly: for $-45$ , start from $-128$ and work out what has to be added to reach $-45$ , which is $83 = 64 + 16 + 2 + 1$ , so the pattern is 1 followed by 1010011.

Converting two's complement to denary

If the MSB is 0, read it as ordinary binary. If the MSB is 1, either add the place values with the MSB worth $-128$ , or invert and add one to find the magnitude and then write a minus sign.

Negative denary to two's complement

Show $-45$ as an 8-bit two's complement integer.

Solution

$+45 = 00101101$

Invert: 11010010

Add 1: 11010011

Check: $-128 + 64 + 16 + 2 + 1 = -45$ .

So $-45 = 11010011$ .

Reading two's complement

The 8-bit pattern 10110110 is stored in a register. State its value as (a) an unsigned integer, (b) a two's complement integer, (c) a one's complement integer.

Solution

(a) Unsigned: $128 + 32 + 16 + 4 + 2 = 182$ .

(b) Two's complement: $-128 + 32 + 16 + 4 + 2 = -74$ .

The same bits mean three different numbers. A bit pattern has no meaning until you know how it is being interpreted.

Binary addition

Binary addition works column by column from the right, exactly as in denary, but you carry whenever a column reaches 2.

Key result

Sum in a column	Write	Carry
$0 + 0$	0	0
$0 + 1$	1	0
$1 + 1$	0	1
$1 + 1 + 1$ (with a carry in)	1	1

Adding two positive numbers

Add the 8-bit binary numbers 00111001 and 00101110. Show your working and check in denary.

Solution


Carry	1	1	1	0	0	0	0
	0	1	1	1	0	0	1
+	0	1	0	1	1	1	0
=	1	1	0	0	1	1	1

The carry row shows the carry into each column, produced by the column to its right.

Result 01100111. Check: $57 + 46 = 103 = 64 + 32 + 4 + 2 + 1$ .

Binary subtraction

Processors do not usually have a separate subtraction circuit. Instead they compute $A - B$ as $A + (-B)$ : find the two's complement of $B$ and add. This is one of the main reasons two's complement is used: one adder circuit does both jobs, and the sign takes care of itself.

Subtracting with two's complement

Write both numbers in the required number of bits.
Find the two's complement of the number being subtracted.
Add the two patterns.
Discard any carry out of the most significant bit.
Read the answer as a two's complement number and check for overflow.

Subtraction giving a negative answer

Use 8-bit two's complement to calculate $23 - 58$ .

Solution

$23 = 00010111$

$58 = 00111010$ , so $-58$ = invert 11000101, add 1 = 11000110.


Carry	0	0	0	1	1	0	0
	0	0	1	0	1	1	1
+	1	1	0	0	1	1	0
=	1	1	1	1	1	0	1

Result 11011101. Value: $-128 + 64 + 16 + 8 + 4 + 1 = -35$ . Check: $23 - 58 = -35$ .

Subtraction with a discarded carry

Use 8-bit two's complement to calculate $77 - 13$ .

Solution

$77 = 01001101$

$13 = 00001101$ , so $-13$ = invert 11110010, add 1 = 11110011.

01001101 + 11110011 = 1 01000000.

The ninth bit is a carry out of the MSB. In two's complement subtraction it is discarded, leaving 01000000 $= 64$ . Check: $77 - 13 = 64$ .

The carry out is not overflow here: a positive and a negative number were added, and the result is in range.

Overflow

Overflow happens when the result of a calculation is too large (or too negative) to fit in the number of bits available. The processor still produces a pattern, but it is wrong.

How you spot overflow depends on how the bits are being interpreted.

Unsigned addition: overflow happens when there is a carry out of the MSB. For example, $200 + 100 = 300$ does not fit in 8 bits (maximum 255).
Two's complement addition: overflow happens when two numbers of the same sign give a result of the opposite sign. Adding a positive and a negative number can never overflow.

Key result

Two's complement overflow rule:

positive + positive giving a negative result: overflow;
negative + negative giving a positive result: overflow;
positive + negative: never overflows (a carry out of the MSB is simply discarded).

In the processor, overflow is recorded by setting the overflow flag in the status register; a carry out of the MSB sets the carry flag.

Overflow with two positives

The 8-bit two's complement numbers 01011010 and 00110111 are added. Show the result and explain whether it is valid.

Solution

01011010 $= 90$ and 00110111 $= 55$ .


Carry	1	1	1	1	1	1	0	0
	0	1	0	1	1	0	1	0
+	0	0	1	1	0	1	1	1
=	1	0	0	1	0	0	0	1

Result 10010001. Its MSB is 1, so as two's complement it means $-128 + 16 + 1 = -111$ .

Two positive numbers have produced a negative result, so overflow has occurred. The true answer, $145$ , is greater than $127$ , the largest 8-bit two's complement value. (As an unsigned number 10010001 is 145, which is correct, and there is no carry out: whether overflow has happened depends on the interpretation.)

Overflow with two negatives

Calculate $-100 + (-50)$ in 8-bit two's complement and comment on the answer.

Solution

$-100$ : $100 = 01100100$ , invert 10011011, add 1 = 10011100.

$-50$ : $50 = 00110010$ , invert 11001101, add 1 = 11001110.

10011100 + 11001110 = 1 01101010. Discard the carry: 01101010 $= +106$ .

Two negative numbers have produced a positive result, so overflow has occurred. The true answer, $-150$ , is below $-128$ and cannot be represented in 8 bits. Using 16 bits would fix this.

Extending to more bits

To store an 8-bit two's complement number in 16 bits, copy the sign bit into all the new positions on the left. This is sign extension: $-45 = 11010011$ becomes 1111111111010011, and $+45 = 00101101$ becomes 0000000000101101. Padding a negative number with zeros would turn it into a large positive number.

Watch out

Inverting without adding one. Inverting the bits gives one's complement, not two's complement. $-45$ is 11010011 in two's complement; 11010010 is the one's complement.

Forgetting the number of bits. The two's complement of a number depends on the word length. Always write the positive number in the full width first: $5 = 00000101$ , not 101, before inverting.

Calling every carry out "overflow". In two's complement, a carry out of the MSB after adding a positive and a negative number is normal and is discarded. Use the sign rule to decide overflow.

Converting the answer as unsigned. After a two's complement calculation, an answer with MSB 1 is negative. Read it with the MSB as $-128$ .

Exam tip

Typical marks for "show $-n$ in two's complement" are one for the correct positive binary and one for the final pattern, so write both lines. For additions, show the carry row; examiners award the working even if one bit slips.

When asked to "explain" an overflow, say three things: the calculation exceeds the range of the representation, state that range (for example $-128$ to $+127$ ), and name the evidence (two positives gave a negative, or there was a carry out of the MSB for unsigned numbers).

If a question says "using two's complement" for a subtraction, you must convert the subtracted number and add; directly subtracting column by column, even if correct, may not earn the method mark.

Summary

Unsigned: all bits positive; 8 bits give 0 to 255.
One's complement: negate by inverting; two zeros; 8 bits give $-127$ to $+127$ .
Two's complement: MSB worth $-2^{n-1}$ ; one zero; 8 bits give $-128$ to $+127$ .
Negate in two's complement by inverting all bits and adding 1.
Subtract by adding the two's complement; discard any carry out of the MSB.
Two's complement overflow: same-sign operands, opposite-sign result. Unsigned overflow: carry out of the MSB.
Sign-extend by copying the MSB leftwards.

Practice

Question

Show $-20$ and $-96$ as 8-bit two's complement integers.
Convert the 8-bit two's complement numbers 11100101 and 01111111 to denary.
State the range of integers that can be represented in 12-bit two's complement.
Write $-77$ in 8-bit one's complement and in 8-bit two's complement.
Add the unsigned 8-bit numbers 01101101 and 00110110, showing the carries. Give the answer in binary and in denary.
Use 8-bit two's complement to calculate $-20 + (-10)$ . Show your working.
Explain why two's complement is preferred to one's complement in processors. Give two reasons.
Calculate $100 + 64$ using 8-bit two's complement. Explain what has happened and how a programmer could prevent it.
The 8-bit registers A and B contain 11001000 and 10110000. They are added and the result is stored in an 8-bit register. (a) Interpreting both as two's complement, state the denary values and the stored result. (b) State whether overflow has occurred, justifying your answer. (c) Interpreting both as unsigned, state whether the stored result is correct.
A 4-bit two's complement system is used. List every bit pattern whose value is negative, with its denary value, and explain why there is one more negative value than positive value.

Answers

$20 = 00010100$ , invert 11101011, add 1: 11101100. $96 = 01100000$ , invert 10011111, add 1: 10100000.
11100101: $-128 + 64 + 32 + 4 + 1 = -27$ . 01111111: $127$ .
$-2^{11}$ to $2^{11} - 1$ , that is $-2048$ to $+2047$ .
$77 = 01001101$ . One's complement $-77$ = 10110010. Two's complement $-77$ = 10110011.
Carries (into each column, left to right) 11111000; result 10100011 = 163. Check $109 + 54 = 163$ .
$-20$ = 11101100, $-10$ = 11110110. Sum = 1 11100010; discard the carry: 11100010 $= -128 + 64 + 32 + 2 = -30$ . Correct, no overflow (two negatives, negative result).
Two's complement has only one representation of zero, so no pattern is wasted and no special zero test is needed; and subtraction can be done by addition with the same adder circuit, with the carry out simply discarded (one's complement needs an "end-around carry" to be added back). It also gives one extra value in the range.
$100 = 01100100$ , $64 = 01000000$ ; sum 10100100 $= -128 + 32 + 4 = -92$ . Two positives gave a negative: overflow, because $164 > 127$ . The programmer could use a larger data type (for example 16 bits) or check the overflow flag after the addition.
(a) 11001000 $= -56$ , 10110000 $= -80$ ; sum 1 01111000, stored result 01111000 $= +120$ . (b) Yes: two negative numbers produced a positive result; the true answer $-136$ is outside $-128$ to $+127$ . (c) Unsigned: $200 + 176 = 376 > 255$ ; there was a carry out of the MSB, so the stored result (120) is also wrong.
1000 $= -8$ , 1001 $= -7$ , 1010 $= -6$ , 1011 $= -5$ , 1100 $= -4$ , 1101 $= -3$ , 1110 $= -2$ , 1111 $= -1$ . Half of the 16 patterns have MSB 1 (eight negatives); the other half have MSB 0, but one of those is zero, leaving only seven positives (1 to 7).

Unsigned binary

One's complement

Two's complement

Converting a negative denary number to two's complement

Converting two's complement to denary

Binary addition

Binary subtraction

Overflow

Extending to more bits

Practice

Console