Signed Int: Bias/Excess Notation

Introduction

The one disadvantage of 2C is that you can't sort the numbers. Suppose you had some hardware that could sort unsigned numbers, or at the very least, compare two unsigned int numbers and tell you which number was larger, or if they were equal.

You couldn't use that hardware to compare two numbers in 2C. In particular, it would say all negative values were larger than non-negative values.

This isn't a big problem, certainly not enough to outweigh the advantages of using 2C for signed ints.

Still, this leads to another idea for representation.

Here's a chart for 3 bit binary numbers using unsigned representation.

Representation Value
000 0
001 1
010 2
011 3
100 4
101 5
110 6
111 7

Suppose we wanted to represent negative numbers, but wanted to keep the same ordering where 000 represents the smallest value and 111 represents the largest value?

This is the idea behind excess representation or biased representation. The bitstring with N 0's maps to the smallest value and the bitstring with N 1's maps to the largest value.

Like SM and 1C, it might be nice if half the bitstrings mapped to negative numbers. Since 3 bits allows for 8 different representations, then half that is 4. So, the smallest value is -4.

When we shift by 4, this is called excess 4 representation. Here's a chart.

Representation Value
000 -4
001 -3
010 -2
011 -1
100 0
101 1
110 2
111 3

In excess notation, you specify two parameters: the number of bits, N, and the bias value, K. In SM and 1C, there's only one parameter: the number of bits.

For example, let K = 5 (in 3 bits), and you have excess 5 representation, which assigns 000 to -5 and makes 111 equal to 2.

In fact, excess K representation maps 0N to -K, and 1N to -K + 2N - 1.

If you pick K = 2N - 1, then the sign bit is flipped, where 1 in the MSb means positive, and 0 means negative.

With excess (or bias) representation, you can't do addition using unsigned int addition hardware. You need a specialized circuit to perform the addition.

Chart

This chart assumes excess K representation.

Number of Bits Number of Values Min Value Max Value
16 216 -K -K + (216 - 1)
32 232 -K -K + (232 - 1)
N 2N -K -K + (2N - 1)

Base 10 to Excess

  1. Add the excess to the base ten number.
  2. Convert the resulting base ten number to unsigned binary (UB).

Excess to Base 10

  1. Convert the binary number to base ten, using unsigned binary (UB) representation.
  2. Subtract the excess.
It's easy to see that converting to and from excess representation are inverse operations.

Why Excess/Bias is Different

The other signed representations we've seen: SM, 1C, and 2C all split the number of negative and non-negative values evenly. In principle, you can do that with excess representation too.

However, since excess K representation using N bits has two parameters, K and N, you can pick K to be whatever you want. You can have more positive numbers than negative, not include zero, and so forth.

Because excess K representation uses two variables (K and N), any hardware designed to perform addition in this representation will depend on both K and N. Fortunately, sorting values in excess representation only depends on N.

Like 2C, excess representation has, at most, one zero. However, it is possible to pick K so there's no zero (pick a suitably large K).

Unlike the other signed int representations, you can compare values in excess/bias representation using unsigned comparison. However, most people prefer doing addition correctly to comparison, which is why 2C is preferred to excess notation.

Excess notation does find a use in floating point representation, however, which is why we study it.