I've started a logic design class where there is a chapter on binary codes and their computing (addition and subtraction).
While I grasp easily the representation of negative values using sign-magnitude, one's complement, and two's complement, I'm confused about the excess-$N$ one.
I've been on Wikipedia and all but I seem not to get it.
Can anyone please explain to me using examples for, let's say, excess-3 and excess-8?
There is also the value of the magic number; in my book it's $2^{(N-1)}$, while on the net I can find $2^{(N+1)}$.
Best Answer
You may find the explanations and charts here ('excess' tab on the slides) helpful; note in particular the complete chart of $3$-bit excess-$4$ notation.
The term magic number refers to a particularly useful value of the shift. The basic idea is to shift the numbers in the representable range so that half of them are positive and half are negative. Of course that’s not actually possible. If you’re using $n$ bits, you can represent $2^n$ different integers. One of them will be $0$, leaving $2^n-1$ that are either positive or negative. But $2^n-1$ is odd, so you can’t make an even split. If you take $2^{n-1}$ as the amount of the shift, so that a string of $n$ zeroes represents the number $-2^{n-1}$, you will be able to represent the $2^{n-1}$ negative integers between $-2^{n-1}$ and $-1$ inclusive, the number $0$, and the $2^{n-1}-1$ positive integers from $1$ through $2^{n-1}-1$; this is as close to an even split as you can get. Moreover, you can tell from the first bit whether a number is negative or not: negative numbers have $0$ as their first bit, while $0$ and the positive integers have a first bit of $1$. In this respect excess-$2^{n-1}$ notation aligns $0$ with the positive integers.
You can come equally close to an even split by using a shift of $2^{n-1}-1$. If you do this, a string of $n$ zeroes represents the integer $-(2^{n-1}-1) = 1 - 2^{n-1}$. When $n=3$, for instance, $000$ now represents $1-2^2 = -3$, not $-4$ as it would in the excess-$4$ notation illustrated on that web page. Now the range of integers that can be represented runs from $-2^{n-1}+1$ through $2^{n-1}$; for $n=3$ that’s from $-3$ through $4$ instead of from $-4$ through $3$. Now the integers with first bit $1$ are positive, and those with first bit $0$ are negative or $0$, so that $0$ is aligned with the negative integers.
The first of these systems is, I think, more common, so magic number for $n$-bit notation usually refers to $2^{n-1}$, but I have seen the term applied to $2^{n-1}-1$ as well, referring to the second of these systems. $2^{n+1}$, however, is simply wrong: either it’s a typo, or it refers to something else altogether.