4
$\begingroup$

Options are:

  1. Signed magnitude
  2. One's complement
  3. Two's complement
  4. Excess notation

This is the question from an 'example of a previous exam' I've been given at university. Answers were not provided. As far as I understand only one answer must be chosen, but I'm not seeing which one.


My attempt at solution

As we see from Signed number representations wikipedia article, both 1. Signed magnitude and 2. One's complement can be chosen as representations requiring the largest amount of memory, because they take up space for both negative and positive 0 (unlike 3. Two's complement and 4. Excess notation).

Is this reasonable, can we say that both 1. and 2. should be chosen as an answers here despite question requiring only one answer?

$\endgroup$
2
$\begingroup$

tl;dr- The intended answer was probably "One's complement" since it wastes encoding on a negative zero. "Signed magnitude" has the same problem, but apparently some sources consider it more efficient because they neglect the sign-bit, presumably under type-erasure logic.

It's also possible that the answer could've been "Excess notation", depending on how they defined it. It's possible to construct excess-notation representations that have degeneracies since multiple combinations of the value and offset could result in the same value. If such degenerate constructions are allowed, then that'd probably have been the intended answer.


Logically, either one's complement or signed-magnitude

I largely agree with @gnasher729's answer in that:

  1. At most, $n_{\text{bits}}$ can encode $2^{n_{\text{bits}}}$ values.

  2. All four formats closely approximate that limit, except two would encode $1$ less value due to having degenerate representations of zero.

  3. Since two formats can have degenerate representations of zero, they'd compete for being the correct answer.

So as @gnasher729 said, it seems like "One's complement" and "Signed magnitude" would be competing for being the correct answer since they both encode only $2^n-1$ distinct values (considering negative zero to be degenerate), whereas the other two encode the full possibility range of $2^n$ distinct values.

Guess: One's compliment is the intended answer

Since two of the answers seem equally valid from a logical perspective, then it seems like it's time to start reverse-engineering what the question-writer was thinking.

Apparently some folks think that one of the two answers, "Signed magnitude", is actually more efficient because it saves a bit:

There were arguments for and against each of the systems. Sign & magnitude allowed for easier tracing of memory dumps (a common process 40 years ago) as small numeric values use fewer 1 bits.

-"Signed number representations", Wikipedia

That seems kinda silly, but I'd speculate that that characterization was in a context in which the signed-bit acted like a sub-type qualifier that may've been removed at some point, kinda like how Java strips generic-type qualifiers.

That wouldn't seem like a fair comparison because it's apple-to-oranges; they're hiding a bit of information in the context. But, if an exam required exactly 1 answer, then it'd seem like guessing against this one may've been a slightly safer bet. Presumably, the course materials may've made the bit-erasure argument at some point.

Possibly excess notation

If we broadly define "excess notation" as representing a value through a combination of two components where one's described as an "offset", then it's possible to construct interpretations where it's possible to represent the same number with multiple combinations of values and offsets.

If this is allowed, then "Excess notation" would've probably been the best answer.

How to answer questions like this on an exam

If this exam were given in a class, ideally the instructor clarified what they meant by these terms and what assumptions should go into them. Then you'd know stuff like if they considered type-erasure for "Signed magnitude" and degenerate representations for "Excess notation".

However if you know all of the logical stuff but don't know what the instructor was thinking, then this strategy might help:

  1. Cross off the answers that probably aren't it, e.g. "Two's complement" is unlikely to be considered a correct answer.

  2. Underline the answers that might be correct, under some sort of logic. For example, "One's compliment" might be correct if we assume type-erasure but don't assume overlapping representations in "Excess notation".

  3. Circle/select the answer that you figure is most likely what the instructor would consider to be correct.

  4. If you have time before the exam's over, you may want to go back and write in quick notes on why each of the underlined answers might be correct.

  5. If the instructor marks the question wrong when you get the exam back, you might go have a discussion with them. Instructors might opt to give students points for a question if they can show that they fully understood the material and merely were unclear about the wording of the question.

$\endgroup$
3
$\begingroup$

The question seems rather bizarre.

Using n bits, each representation can represent $2^n$ different values. Two of them have different representations for +0 and -0. I would assume that signed-magnitude and one's complement are used if someone values the ability to distinguish +0 and -0.

If the question was "which representation takes the largest amount of memory", then that question is already nonsense because no matter what you think about +/- 0, one's complement and signed magnitude are the same. If the question was "which representations take the largest amount of memory", then I'd still say that claiming one (or two) take more than the others is very misguided.

(And the number $-2^{n-1}$ that can be represented with n bits two's complement or signed magnitude has its own problems where both negation and division can lead to overflow).

$\endgroup$
  • $\begingroup$ Thank you for mentioning that some may value the ability to have both +0 and -0. $\endgroup$ – lakesare Jan 1 '18 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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