2.2 Signed Integers: Signed Magnitude & Complements

Theory: Signed Integers: Signed Magnitude & Complements

A computer stores numbers in fixed-size binary words (8, 16, 32, 64 bits). Unsigned binary only covers $0, 1, 2, \dots$ The question for this section is: how do we encode negative numbers using only 0s and 1s? There is no “minus” symbol in hardware, so one of the bits has to carry the sign information. There are three main methods (Null & Lobur, Ch. 2):

Signed magnitude
One’s complement
Two’s complement

Throughout, $n$ is the word size in bits and the leftmost bit (MSB) is the sign bit in all three schemes: $0$ = positive, $1$ = negative. Positive numbers look identical in all three; they differ only in how negatives are formed.

Signed Magnitude

Idea: copy what we do on paper. Use the leftmost bit for the sign and the remaining $n - 1$ bits for the magnitude (absolute value) in ordinary binary.

 sign | magnitude (n-1 bits)
  0   | 0010010      = +18
  1   | 0010010      = -18

Range for $n$ bits: $-(2^{n-1} - 1)$ to $+(2^{n-1} - 1)$ . For 8 bits: $-127$ to $+127$ .

Problems:

Two representations of zero: $0\,0000000 = +0$ and $1\,0000000 = -0$ . Testing “is it zero?” needs two comparisons.
Arithmetic is awkward: the hardware must look at both signs, compare magnitudes, decide whether to add or subtract, and choose the sign of the result (section 2.3).

Mini-example

$+18 = 0\,0010010$ , $-18 = 1\,0010010$ . Only the sign bit changes.

One’s Complement

Idea: represent $-N$ by the complement of $N$ with respect to $2^n - 1$ (all ones):

-N \;\longrightarrow\; (2^n - 1) - N

Subtracting from all ones never borrows, so this is the same as flipping every bit ( $0 \leftrightarrow 1$ ). That is trivial to build in hardware (one NOT gate per bit).

For 4 bits: one’s complement of $0100$ is $1111 - 0100 = 1011$ , which is just $0100$ with every bit flipped.

Range for $n$ bits: $-(2^{n-1} - 1)$ to $+(2^{n-1} - 1)$ , same as signed magnitude.

Advantage: subtraction becomes addition, $5 - 2 = 5 + (-2)$ , using the same adder (section 2.3).

Disadvantages: still two zeros ( $00\cdots0 = +0$ and $11\cdots1 = -0$ ), and addition needs an extra step (the end-around carry).

Mini-example

$19 = 00010011$ , so $-19$ in one’s complement is $11101100$ (every bit flipped).

Two’s Complement

Idea: represent $-N$ by the complement with respect to $2^n$ :

-N \;\longrightarrow\; 2^n - N = \big((2^n - 1) - N\big) + 1

So: two’s complement = one’s complement + 1 (“flip all the bits, then add 1”).

Shortcut: scan from the right, copy every bit up to and including the first 1, then flip all the remaining bits to the left. Example: $44 = 0010\,1100$ . Copy the rightmost " $100$ ", flip the rest " $00101$ " → " $11010$ ": $-44 = 1101\,0100$ .

Range for $n$ bits: $-2^{n-1}$ to $+(2^{n-1} - 1)$ . For 4 bits: $-8$ to $+7$ ; for 8 bits: $-128$ to $+127$ . One extra negative value, because there is only one zero.

Reading a two’s complement number: the MSB has weight $-2^{n-1}$ instead of $+2^{n-1}$ :

b_{n-1} b_{n-2} \cdots b_0 = -b_{n-1} \times 2^{n-1} + \sum_{i=0}^{n-2} b_i \times 2^i

Alternatively, if the sign bit is 1, take the two’s complement again to get the magnitude.

Advantages: one zero; addition and subtraction use a plain adder with no correction step (just discard the carry out of the MSB); larger range.

Mini-example

$19 = 00010011$ → flip → $11101100$ → add 1 → $-19 = 11101101$ . Check with weights: $-128 + 64 + 32 + 8 + 4 + 1 = -19$ ✓.

Ranges for $n$ Bits

Representation	Smallest	Largest	4 bits	8 bits	16 bits	Zeros
Unsigned	$0$	$2^n - 1$	0 to 15	0 to 255	0 to 65535	one
Signed magnitude	$-(2^{n-1}-1)$	$2^{n-1}-1$	−7 to +7	−127 to +127	−32767 to +32767	two
One’s complement	$-(2^{n-1}-1)$	$2^{n-1}-1$	−7 to +7	−127 to +127	−32767 to +32767	two
Two’s complement	$-2^{n-1}$	$2^{n-1}-1$	−8 to +7	−128 to +127	−32768 to +32767	one

Comparing the Three on 3 Bits

Pattern	Signed magnitude	One’s complement	Two’s complement
000	+0	+0	+0
001	+1	+1	+1
010	+2	+2	+2
011	+3	+3	+3
100	−0	−3	−4
101	−1	−2	−3
110	−2	−1	−2
111	−3	−0	−1

The three patterns with sign bit 0 agree; the four with sign bit 1 differ.

Sign Extension

To widen a number to more bits without changing its value:

Representation	Rule
Two’s complement / one’s complement	Copy the sign bit into all the new high-order positions.
Signed magnitude	Move the sign bit to the new MSB and fill the new positions between the sign and the magnitude with 0s.
Unsigned	Fill with 0s (zero extension).

Mini-example

$-3$ in 4-bit two’s complement is $1101$ . In 8 bits: $1111\,1101$ (check: $256 - 3 = 253 = 11111101_2$ ✓). Padding with zeros instead ( $0000\,1101 = +13$ ) would be wrong.

Which Representation Is Best, and Why?

Judge them on three issues: (1) balance (as many negatives as positives?), (2) number of zeros, (3) ease of operations.

Issue	Signed magnitude	One’s complement	Two’s complement
Balance	balanced	balanced	one extra negative
Zeros	two (+0, −0)	two (+0, −0)	one
Ease of operations	worst: sign logic, compare magnitudes, separate subtractor	addition only, but end-around carry	addition only, carry simply discarded

Two’s complement is the best and is what virtually every modern computer uses for integers: one unique zero (simpler zero tests), the widest range, and subtraction done by the same adder with no correction step. The slight imbalance (e.g. $-128$ has no positive partner in 8 bits) is a small price.

Worked Examples

Exercise 1

Represent $+18$ , $-18$ , $+100$ and $-100$ as 8-bit numbers in signed magnitude, one’s complement and two’s complement.

Show solution ↓

Solution

First write the magnitudes in 8-bit binary:

$18 = 16 + 2 = 0001\,0010_2$
$100 = 64 + 32 + 4 = 0110\,0100_2$

Positives are the same in all three systems. For the negatives:

Signed magnitude: set the sign bit to 1, keep the magnitude.
One’s complement: flip every bit of the positive pattern.
Two’s complement: one’s complement + 1.

Value	Signed magnitude	One’s complement	Two’s complement
$+18$	0001 0010	0001 0010	0001 0010
$-18$	1001 0010	1110 1101	1110 1110
$+100$	0110 0100	0110 0100	0110 0100
$-100$	1110 0100	1001 1011	1001 1100

Checks (two’s complement $-N = 2^8 - N$ ): $256 - 18 = 238 = 1110\,1110_2$ ✓ and $256 - 100 = 156 = 1001\,1100_2$ ✓. One’s complement ( $255 - N$ ): $237 = 1110\,1101_2$ ✓ and $155 = 1001\,1011_2$ ✓.

Exercise 2

(a) Given $19 = 00010011_2$ , find $-19$ in 8-bit one’s complement and two’s complement.

(b) Find $-44$ in 8-bit two’s complement using the copy-then-flip shortcut, and check it two other ways.

Show solution ↓

Solution

(a) One’s complement: flip every bit.

0001\,0011 \;\to\; 1110\,1100 \quad (-19 \text{ in one's complement})

Two’s complement: add 1 to the one’s complement.

1110\,1100 + 1 = 1110\,1101 \quad (-19 \text{ in two's complement})

Check: $1110\,1101_2 = 237 = 256 - 19$ ✓.

(b) $44 = 32 + 8 + 4 = 0010\,1100_2$ .

Scan from the right: the first 1 is at bit 2. Copy " $100$ ", flip the remaining five bits " $00101$ " → " $11010$ ":

-44 = 1101\,0100

Check 1 (flip + 1): $0010\,1100 \to 1101\,0011 \to 1101\,0011 + 1 = 1101\,0100$ ✓.

Check 2 (weights): $-128 + 64 + 16 + 4 = -44$ ✓.

Exercise 3

What decimal value does the 8-bit pattern $1011\,0101$ represent if it is interpreted as (a) unsigned, (b) signed magnitude, (c) one’s complement, (d) two’s complement? Repeat for $0110\,1001$ .

Show solution ↓

Solution

Pattern $1011\,0101$ (sign bit is 1):

(a) Unsigned: $128 + 32 + 16 + 4 + 1 = 181$ .

(b) Signed magnitude: sign 1 (negative), magnitude $011\,0101_2 = 32 + 16 + 4 + 1 = 53$ . Value $= -53$ .

(c) One’s complement: negative, so flip to get the magnitude: $0100\,1010_2 = 64 + 8 + 2 = 74$ . Value $= -74$ . (Check: $181 - 255 = -74$ ✓.)

(d) Two’s complement: negative, so flip and add 1: $0100\,1010 + 1 = 0100\,1011_2 = 75$ . Value $= -75$ . (Check with weights: $-128 + 32 + 16 + 4 + 1 = -75$ ✓, or $181 - 256 = -75$ ✓.)

Pattern $0110\,1001$ : the sign bit is 0, so it is positive and all four interpretations agree:

64 + 32 + 8 + 1 = +105 \text{ in every representation.}

For negative patterns, the three signed readings always differ: one’s complement is the two’s complement value $+1$ (here $-74$ vs $-75$ ), and signed magnitude is something else entirely.

Exercise 4

(a) Give the range of values for 4-bit, 8-bit and 16-bit two’s complement, and for 8-bit signed magnitude.

(b) What is the minimum number of bits needed to store $-200$ in two’s complement? In signed magnitude?

Show solution ↓

Solution

(a) Two’s complement range is $-2^{n-1}$ to $2^{n-1} - 1$ :

$n$	Range
4	$-2^3$ to $2^3 - 1$ = $-8$ to $+7$
8	$-2^7$ to $2^7 - 1$ = $-128$ to $+127$
16	$-2^{15}$ to $2^{15} - 1$ = $-32768$ to $+32767$

8-bit signed magnitude: $-(2^7 - 1)$ to $2^7 - 1$ = $-127$ to $+127$ (one fewer negative value, because $1000\,0000$ is $-0$ ).

(b) Two’s complement needs $-2^{n-1} \le -200$ , i.e. $2^{n-1} \ge 200$ . Since $2^7 = 128 \lt 200 \le 256 = 2^8$ , we need $n - 1 = 8$ , so $n = 9$ bits. ( $-200 = 1\,0011\,1000_2$ : check $-256 + 32 + 16 + 8 = -200$ ✓.)

Signed magnitude needs $2^{n-1} - 1 \ge 200$ , so $2^{n-1} \ge 201$ , again $n = 9$ bits (sign bit + 8-bit magnitude $200 = 1100\,1000_2$ , giving $1\,1100\,1000$ ).

Exercise 5

Build the table of all 3-bit patterns and their values in signed magnitude, one’s complement and two’s complement. Then answer: how many distinct values can each scheme represent with 3 bits, and which patterns are “wasted”?

Show solution ↓

Solution

Positive patterns (sign bit 0) mean the same thing in all three. For sign bit 1:

Signed magnitude: $1xy = -(xy_2)$ .
One’s complement: flip all bits to get the magnitude.
Two’s complement: weight of MSB is $-4$ , so $1xy = -4 + xy_2$ .

Pattern	Signed magnitude	One’s complement	Two’s complement
000	+0	+0	+0
001	+1	+1	+1
010	+2	+2	+2
011	+3	+3	+3
100	−0	−3 (flip: 011)	−4 ( $-4+0$ )
101	−1	−2 (flip: 010)	−3 ( $-4+1$ )
110	−2	−1 (flip: 001)	−2 ( $-4+2$ )
111	−3	−0 (flip: 000)	−1 ( $-4+3$ )

Signed magnitude: 8 patterns but only 7 distinct values ( $-3$ to $+3$ ); $100$ ( $-0$ ) duplicates zero.
One’s complement: also 7 distinct values ( $-3$ to $+3$ ); $111$ ( $-0$ ) duplicates zero.
Two’s complement: all 8 patterns give distinct values ( $-4$ to $+3$ ); no pattern is wasted.

This is exactly why two’s complement has the larger range.

Exercise 6

Sign-extend $+5$ and $-5$ from 4 bits to 8 bits in each of the three representations.

Show solution ↓

Solution

4-bit forms: $+5 = 0101$ in all three. $-5$ : signed magnitude $1101$ , one’s complement $1010$ , two’s complement $1011$ .

Value	Scheme	4-bit	8-bit	Rule used
$+5$	all three	0101	0000 0101	sign bit 0 copied / zeros inserted
$-5$	signed magnitude	1101	1000 0101	sign moves to MSB, zeros inserted after it
$-5$	one’s complement	1010	1111 1010	copy sign bit 1
$-5$	two’s complement	1011	1111 1011	copy sign bit 1

Checks: one’s complement $255 - 5 = 250 = 1111\,1010_2$ ✓; two’s complement $256 - 5 = 251 = 1111\,1011_2$ ✓; signed magnitude $1\,000\,0101$ = sign − , magnitude 5 ✓.

Exercise 7

Considering balance, number of zeros and ease of operations, which of the three representations is best? Justify your answer with a short example.

Show solution ↓

Solution

Two’s complement is best.

Balance: signed magnitude and one’s complement are perfectly balanced ( $-127$ to $+127$ in 8 bits); two’s complement has one extra negative ( $-128$ to $+127$ ). This is a minor drawback.
Number of zeros: signed magnitude and one’s complement each have two zeros ( $+0$ and $-0$ ), so a test for zero must check two patterns and one pattern is wasted. Two’s complement has a single zero ( $0000\,0000$ ).
Ease of operations: in two’s complement, subtraction is just addition of the negated number, and any carry out of the MSB is discarded. Example (8 bits), $48 + (-19)$ :

   0011 0000   (48)
 + 1110 1101   (-19)
 -----------
 1 0001 1101   -> discard carry -> 0001 1101 = 29

In one’s complement the same addition needs an extra end-around-carry addition; in signed magnitude the hardware must compare signs and magnitudes and subtract.

Hence two’s complement gives the simplest, fastest hardware and the largest range, which is why it is the standard for integers.

2.2 Signed Integers: Signed Magnitude & Complements

Theory: Signed Integers: Signed Magnitude & Complements

Signed Magnitude

Mini-example

One’s Complement

Mini-example

Two’s Complement

Mini-example

Ranges for nnn Bits

Comparing the Three on 3 Bits

Sign Extension

Mini-example

Which Representation Is Best, and Why?

Worked Examples

Ranges for $n$ Bits