Excess

This last common representation tries to mitigate the jump from largest number to the smallest number when we increment by one. The problem with the jump is comparing two numbers requires additional check. Consider comparing 7, 3, -2 and -4 in a 4-bit numbers.

How would we compare two numbers in different representation? The easiest will be comparing two positive numbers. In such cases, we simply compare the binary representation.

Next, consider comparing positive and negative number. To find the larger number, we simply have to check the first bit and ignore the rest. Now, for the real problem. When we compare two negative numbers like -2 and -4, it is not enough to just ignore the first bit and compare the rest of the bits:

• Sign-and-Magnitude: The larger number is number where the rest of the bits is smaller as it corresponds to the magnitude.
• 1s Complement & 2s Complement: The larger number is the number where the rest of the bits is larger.

So now, we have a rather complex operations involving selections to check if a number A is smaller than number B. The pseudo-codes for each representation is written below. Here, we use a Pythonic notation where A[0] is the left-most bit and A[1:] is the rest of the bits.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# input : number A in sign-and-magnitude
#         number B in sign-and-magnitude
# output: Boolean C = A < B
if A[0] == B[0] then  # equal sign
  if A[0] == 0 then   # positive
    C = A < B
  else                # negative
    C = A[1:] > B[1:]
  end
else
  C = A[0] < B[0]
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# input : number A in 1s complement
#         number B in 1s complement
# output: Boolean C = A < B
if A[0] == B[0] then  # equal sign
  if A[0] == 0 then   # positive
    C = A < B
  else                # negative
    C = A[1:] < B[1:]
  end
else
  C = A[0] < B[0]
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# input : number A in 2s complement
#         number B in 2s complement
# output: Boolean C = A < B
if A[0] == B[0] then  # equal sign
  if A[0] == 0 then   # positive
    C = A < B
  else                # negative
    C = A[1:] < B[1:]
  end
else
  C = A[0] < B[0]
end

The next representation we are discussing is solving this exact problem. In particular, we will remove the need for selection statement to compare two numbers. Consider the cause of this problem. The root cause is that when we keep on incrementing the binary representation by 1, there is a discontinuity in the decimal value.

To remove this discontinuity, we simply state we do not start counting from 0 but instead, count from some number N. In other words, given a sequence of bits, we simply convert it into decimal and then add/subtract some value according to the starting number N.

Representation

Excess representation requires two values, the starting number and the number of bits. We then let the representation 000...00 to represent the starting number.

However, the naming convention can be rather weird. Let's illustrate this with a concrete example. Consider the following number:

• Starting number is -4
• Number of bits is 3

We call this representation Excess-4 representation on 3-bit numbers. The numbers are listed below.

In general, if we have Excess-N on M-bit numbers, we have:

• Starting number is -N
• Number of bits is M

Properties

Range

Ideally, we want the number to be evenly distributed between positive and negative value. We can do this by starting from the default range between 0 and 2ⁿ-1. Then we translate the value so that the starting number is not 0. The translation can be done by either addition/subtraction.

Using a simple calculation, to make it evenly distributed, we simply halve the largest value. So, instead of 2ⁿ-1, we should have 2^n-1-1¹. Hence, the smallest number should be -2^n-1.

As we have seen from the case of Excess-4 on 3-bit numbers above, we get a roughly equal number of positive and negative. The number 4 was chosen by the calculation. Since the smallest number is -2^n-1 = -2^3-1 = -2² = -4, the representation should be Excess-4. Uneven distribution may be used but it is uncommon.

Arithmetic

Unfortunately, addition is not as simple as binary addition. To illustrate, consider adding -4 + -3 for Excess-4 on 3-bit numbers.

1
2
3
4

000
001
--- +
001

Clearly, it is wrong. The advantage of Excess-N representation is really just comparing two numbers. In this case, comparing two Excess-N numbers is really just comparing their binary representation directly as if they are decimal values. This can be directly inferred from the fact that Excess-N numbers are just translation of binary numbers (i.e., shifted by additiong/subtraction).

?? info "Floating Point" The number 7 can be computed from 2^n-1-1 instead of 2^n-1. This favours positive numbers more than negative numbers. IEEE floating point standards uses the former method of 2^n-1-1 instead of the latter method 2^n-1 for the exponent.