Signed Int: Signed Magnitude

Introduction

If someone had just learned about unsigned int, and you asked them to invent a way to represent negative numbers, I would think the vast majority of them would invent signed magnitude.

The concept of signed magnitude is easy enough. Make the most significant bit the sign bit. If this bit is 1, then the value is negative. If it's 0, the value is positive.

Base Ten to Signed Magnitude

Here's the algorithm to convert base 10 (decimal) to signed magnitude using N bits. From now on, we'll include the number of bits when talking about representations. Thus, it's not just signed magnitude, but signed magnitude using N bits.

Ignore the minus sign (if it appears) and convert the base 10 value to binary.
If the binary representation doesn't have N-1 bits, pad it to N-1 bits with 0s. For example, if the binary representation only needs k bits, then set b_(N-2)-k to 0^(N-2)-k where 0^N means N zeroes. (This is where it's useful to think of a bitstring as a string).
If the value is positive, make b_N-1 = 0. If it's negative, then make b_N-1 = 1.

It's not that hard really. For a 32-bit bitstring, convert the value to unsigned 31-bit bitstring, and add a sign bit, to indicate the sign.

We'll use SM as a shorthand for signed magnitude, so I don't have to write that out every single time.

SM to Base 10

Converting SM to base 10 isn't that hard either. It's the reverse process.

Consider only the bottom N-1 bits of the number, i.e. b_(N-2)-0. (That is, ignore the sign bit). Convert that to base 10, which will produce a non-negative value.
If the sign bit is 1, then add a negative sign to the base 10 value. Otherwise, don't.

An Example

Suppose you want to represent 3 in SM using 4 bits. Since 3 is positive, you just convert it to base 2 to get 11. However, we need 4 bits, so we pad to 4 bits, to get 0011.

Suppose you want to represent -3 in SM using 4 bits. Since -3 is negative, convert 3 to 3 bits, unsigned, and you get 011. The number is negative, so add a sign bit of 1, to get 1011.

Another way to do the same thing is to convert 3 to 4 bits, and flip the sign bit.

Suppose you want to represent 15 in SM using 4 bits. The rule normally says to convert to base 2. This results in 1111. Unfortunately, if you convert it back, that's -7.

So what went wrong? It turns out that 15 is larger than the largest possible representable number using 4 bits in SM. That is, you CAN'T represent 15 using 4 bits (you can with 5 bits).

This is a common phenomenon. Because you have a finite number of bits, you also only have a finite number of values that can be represented. Some values can't be represented given a certain number of bits.

We'll discuss, in the next section, what the range of valid values are, given N bits, so you know what values can and can't be translated to SM with N bits.

How Many Positive/Negative Values?

You know, by now, that N bits produces 2^N different bitstrings. If half of these are positive, then there are 2^N/2 = 2^N-1 positive values. There should also be 2^N-1 negative values, too.

Let's focus on the positive values. You know that the most significant bit is already 0. This really means that you only have N-1 bits to use represent positive values. The question then reduces to, what's the maximum value for N-1 bits.

The answer is 2^N-1 - 1 (just plug in N-1 to the unsigned maximum value).

Fortunately, it's very easy to determine the minimum value. Make the sign bit 1 for the maximum, and it's now the largest (magnitude) negative value. So, the minimum value is -(2^N-1 - 1).

Problem: Two Zeroes

One problem we'll run into is SM has two zeroes. There's a positive zero (represented by a bitstring with N zeroes), and a negative zero (represented by a bitstring with 1 followed by N-1 zeroes).

This creates problems because when you want to compare or add two numbers, you need hardware to take that into account. It's not that it can't be done quickly, but that it seems to add complication to this, otherwise, convenient way to represent signed ints.

Another observation: we have two representations for the same value. This is why it's important to note the number of values. We have 2^N representations, but we have 2^N - 1 values. We have one less value because zero appears twice.

So, it's not that unusual to see more than one representations mapping to the same value.

Problem: Addition

It would be nice if adding signed ints was just like adding unsigned ints. That way, the hardware for adding unsigned and signed ints would be the same.

However, this doesn't work. For example, consider adding -1 and -1 using 4 bits SM. That's 1001 + 1001 = 0010 (since the result must be four bits, we ignore the carry of 1, into the b₄, that is, normally, the answer is 10010, which is 5 bits, but we ignore that most significant bit, to keep the answer to 4 bits).

The answer is +2, which is incorrect. It should be -2. One way around this problem is to add everything, but ignore the sign bit. Then, we keep the same sign bit as before. Thus, when we add -1 to -1, we get 2, and then preserve the sign bit to get -2.

That works fine if you add two positive numbers and two negative numbers. But what happens if you add a positive and a negative number. Then, you have problems. For example, add 1 to -1, and you have 0001 + 1001, which adds to 1010, or -2. The answer should be 0.

Again, one could design a circuit that does addition correctly for SM, but it would have to be a different circuit from the one that adds correctly for unsigned ints.

Negating

Students often confuse the following: representing a negative number and negating a value. To negate a value means to take some value x and compute -x. The result of -x might actually be positive, if x is negative to begin with.

The key difference is representation versus performing an operation. Negating a value means to perform an operation. You can negate a value, then negate the result of the negation and so on.

One key property of negation is: --x = x. That is, if you negate x twice, you get back the original value.

Fortunately, it's quite easy to negate an SM number. You flip the most significant bit. To flip a bit means to replace it with its "opposite" value. Thus, flipping a 0 produces a 1. Flipping a 1 produces a 0.

We can write this as b_N-1 = b_N-1' (for an N bit SM representation). The prime (which looks like an apostrophe) is the negation. This is logical NOT, which you should have seen in a discrete math course. The prime appears RIGHT of the bit it is negating.

Chart

Number of Bits	Number of Values	Min Value	Max Value
16	2¹⁶ - 1	-(2¹⁵ - 1)	2¹⁵ - 1
32	2³² - 1	-(2³¹ - 1)	2³¹ - 1
N	2^N - 1	-(2^N-1 - 1)	2^N-1 - 1

Conclusion

SM is a first attempt at representing signed int (i.e., positive, negative, and zero). The main advantage of this scheme is that it's obvious. However, SM has some problems. It has two zeroes. You can't use the same hardware for adding as unsigned int. These aren't insurmountable problems. However, if there are better representations without such problems, we'd want to consider them.

Web Accessibility