Heading 1

Representing Integers

Unbounded Case

The unsigned integers are:

0, 1, 2, 3, etc.

If N is an unsigned integer, then we can represent it as a sum of powers of a fixed base:

N = d[0] * b^0 + d[1] * b^1 + d[2] * b^2 + etc.

where:

0 <= d[i] < b

There are four popular bases:

0bN = base 2 or binary representation of N 0N = base 8 or octal representation of N N = base 10 or decimal representation of N 0xN = base 16 or hexadecimal representation of N.

Readers should consult the book to learn algorithms for converting between the bases. For example:

42 = 4 * 10^1 + 2 * 10^0 = 0x2a = 2 * 16^1 + 10 * 16^0 = 052 = 5 * 8^1 + 2 * 8^0 = 0b101010 = 1 * 2^5 + 0 * 2^4 + 1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 0 * 2^0

Bounded Case

Assume

sizeof(WORD) = 4 bits

This means a register or memory cell can only hold 4 bits. What is the range of numbers we can represent on this machine? If by number we mean unsigned integer, then there are 2^4 = 16 possible combinations:

0b0000 = 0x0 = 0 0b0001 = 0x1 = 1 0b0010 = 0x2 = 2 0b0011 = 0x3 = 3 0b0100 = 0x4 = 4 0b0101 = 0x5 = 5 0b0110 = 0x6 = 6 0b0111 = 0x7 = 7 0b1000 = 0x8 = 8 0b1001 = 0x9 = 9 0b1010 = 0xa = 10 0b1011 = 0xb = 11 0b1100 = 0xc = 12 0b1101 = 0xd = 13 0b1110 = 0xe = 14 0b1111 = 0xf = 15

Note: Our convention is to preface binary numbers with 0b and hexadecimal (base 16) numbers with 0x. Decimal numbers have no prefix.

If we are to include signed numbers, then obviously we will only be able to represent about half as many non-negative numbers. Generally, there are three types of computers. Computers that represent signed integers using the Sign-Magnitude system, computers that represent signed integers using the Ones-Complement system, and computers that represent signed integers using the Twos-Complement system. Although the Twos Complement system is the most popular, you will be expected to know all three systems.

All three sy7stems have several features in common. First, the representation of the nonnegative integers is the same in all three systems:

0b0000 = 0x0 = 0 0b0001 = 0x1 = 1 0b0010 = 0x2 = 2 0b0011 = 0x3 = 3 0b0100 = 0x4 = 4 0b0101 = 0x5 = 5 0b0110 = 0x6 = 6 0b0111 = 0x7 = 7

Second, the most-significant bit (MSB) always indicates the sign: 1 = negative, 0 = positive.

In the Sign-Magnitude system we negate a number by flipping the MSB. Thus:

0b1000 = 0x8 = -0 0b1001 = 0x9 = -1 0b1010 = 0xa = -2 0b1011 = 0xb = -3 0b1100 = 0xc = -4 0b1101 = 0xd = -5 0b1110 = 0xe = -6 0b1111 = 0xf = -7

One embarrassing feature of this system is that 0 and -0 have different representations!

In the Ones-Complement system we negate a number by subtracting it from 15. 15 is called the bias, and it is always the largest unsigned number that can be represented. For example:

~6 = 15 - 6 = 9 ~(~6) = 15 - 9 = 6

We use ~x to denote the Ones-Complement negation of x, because in C--/C/C++/Java we are allowed both the Ones and Two complement of a number.

There's an easy trick for computing ~x, simply flip every bit of x. Thus:

0b1111 = 0xf = ~0 0b1110 = 0xe = ~1 0b1101 = 0xd = ~2 0b1100 = 0xc = ~3 0b1011 = 0xb = ~4 0b1010 = 0xa = ~5 0b1001 = 0x9 = ~6 0b1000 = 0x8 = ~7

Again we have the awkwardness of different representations for 0 and ~0.

In the Twos-Complement system numbers are negated by subtracting them from 16, the smallest unsigned integer that can't be represented. For example:

-6 = 16 - 6 = 10 -(-6) = 16 - 10 = 6

The easy way to compute the Twos complement of x is to use the formula:

-x = ~x + 1

Thus:

0b1111 = 0xf = -1 0b1110 = 0xe = -2 0b1101 = 0xd = -3 0b1100 = 0xc = -4 0b1011 = 0xb = -5 0b1010 = 0xa = -6 0b1001 = 0x9 = -7 0b1000 = 0x8 = -8

One awkward feature of this system is that we have a representation for -8, but no representation for +8!

-(-8) = ~8 + 1 = 0b0111 + 1 = 0b1000 = 8