2.6: Detail - Integer Codes

There are many ways to represent integers as bit patterns. All suffer from an inability to represent arbitrarily large integers in a fixed number of bits. A computation which produces an out-of-range result is said to overflow.

The most commonly used representations are binary code for unsigned integers (e.g., memory addresses), 2’s complement for signed integers (e.g., ordinary arithmetic), and binary gray code for instruments measuring changing quantities.

The following table gives five examples of 4-bit integer codes. The MSB (most significant bit) is on the left and the LSB (least significant bit) on the right.

Table 2.3: Four-bit integer codes

	\(\overbrace{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad}^{\text{Unsigned Integers}}\)		\(\overbrace{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}^{\text{Signed Integers}}\)
	Binary Code	Binary Gray Code	2's Complement	Sign/Magnitude	1's Complement
\(\text{Range}\rightarrow\)	[0, 15]	[0, 15]	[-8, 7]	[-7, 7]	[-7, 7]
-8			1000
-7			1001	1111	1000
-6			1010	1110	1001
-5			1011	1101	1010
-4			1100	1100	1011
-3			1101	1011	1100
-2			1110	1010	1101
-1			1111	1001	1110
0	0000	0000	0000	0000	0000
1	0001	0001	0001	0001	0001
2	0010	0011	0010	0010	0010
3	0011	0010	0011	0011	0011
4	0100	0110	0100	0100	0100
5	0101	0111	0101	0101	0101
6	0110	0101	0110	0110	0110
7	0111	0100	0111	0111	0111
8	1000	1100
9	1001	1101
10	1010	1111
11	1011	1110
12	1100	1010
13	1101	1011
14	1110	1001
15	1111	1000

Binary Code

This code is for nonnegative integers. For code of length \(n\), the 2\(^n\) patterns represent integers 0 through 2\(^n\) − 1. The LSB (least significant bit) is 0 for even and 1 for odd integers.

Binary Gray Code

This code is for nonnegative integers. For code of length \(n\), the 2\(^n\) patterns represent integers 0 through 2\(^n\)−1. The two bit patterns of adjacent integers differ in exactly one bit. This property makes the code useful for sensors where the integer being encoded might change while a measurement is in progress. The following anonymous tribute appeared in Martin Gardner’s column “Mathematical Games” in Scientific American, August, 1972, but actually was known much earlier.

The Binary Gray Code is fun, f

or with it STRANGE THINGS can be done...

Fifteen, as you know, is one oh oh oh,

while ten is one one one one.

2's Complement

This code is for integers, both positive and negative. For a code of length \(n\), the 2\(^n\) patterns represent integers −2\(^{n−1}\) through 2\(^{n−1}\) −1. The LSB (least significant bit) is 0 for even and 1 for odd integers. Where they overlap, this code is the same as binary code. This code is widely used.

Sign/Magnitude

This code is for integers, both positive and negative. For code of length \(n\), the 2\(^n\) patterns represent integers −(2\(^{n−1}\) − 1) through 2\(^{n−1}\) − 1. The MSB (most significant bit) is 0 for positive and 1 for negative integers; the other bits carry the magnitude. Where they overlap, this code is the same as binary code. While conceptually simple, this code is awkward in practice. Its separate representations for +0 and -0 are not generally useful.

1's Complement

This code is for integers, both positive and negative. For code of length \(n\), the 2\(^n\) patterns represent integers −(2\(^{n−1}\) − 1) through 2\(^{n−1}\) − 1. The MSB is 0 for positive integers; negative integers are formed by complementing each bit of the corresponding positive integer. Where they overlap, this code is the same as binary code. This code is awkward and rarely used today. Its separate representations for +0 and -0 are not generally useful.