Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)}$.

share|improve this question
add comment

2 Answers 2

Excess-N notation shifts all values by N. That is, in excess-N notation, the number represented by a binary code is N less than the unsigned value you would normally assign to that code.

For example, in excess-3 notation, the string '0000' (which is 0 in unsigned binary) represents 0 - 3 = -3. The string '0100' (which is 4 in unsigned binary) represents 4 - 3 = 1.

It's quite common to see excess-N notation when denoting the exponent of a floating point numbers. For example, 32-bit floating point numbers often use 8 bits in excess-127 notation to represent the exponent.

share|improve this answer
add comment

You may find the explanations and charts here 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.

share|improve this answer
    
@brian-m-scott Can you check this from your link: "In fact, excess K representation maps 0^N to -K, and 1^N to -K + 2^N - 1" I have doubts about 1^N Below the second chart. –  MIH1406 Sep 24 '12 at 3:44
1  
@MIH1406: It’s okay: $1^N$ means $\underbrace{1\dots 1}_n$, a string of $n$ $1$’s, which is the binary representation of $2^N-1$, so it represents $2^N-1$ more than $0^N=\underbrace{0\dots 0}_n$ does. The latter represents $-K$, so the former represents $-K+2^N-1$. –  Brian M. Scott Sep 24 '12 at 3:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.