1.2 Signed Representations¶

This note focuses more on how to represent more types of numbers using signed representations, in particular, sign-magnitude, twos-complement, and biased representations. We will be paying particular focus of signed representations with respect to binary and hexadecimal number systems. Get back to toc CS61C or 1. Number Representation

Other Number Representations¶

So far, we only know how to describe positive numbers in range $[0, 2^n-1]$. However, we need to expand into trying to represent other numbers, like negative numbers, or even numbers competely in different ranges. There are three representations we will look at, and for each, we will discuss how they succeed in answering the following questions. 1. How many unique values are represented by this system? 2. What is the range that the numbers can represent? 3. How easy is it to do math with?

Sign-Magnitude Representation¶

In our decimal number system, we simply tack on a negative sign in front of our decimal number to indicate its sign. However, computers cannot recognize a negative sign, they only can interpret a 0 or 1. Therefore, it feels natural to let the most significant bit (MSB) to indicate sign, where bit 0 indicates positive, and 1 indicates negative. Therefore, to convert a possibly negative decimal number into sign-magnitude binary representation, the procedure would look like 1. Disregard the sign in front for now. Convert the magnitude of the number to binary 2. If the decimal number was negative, concatenate with a 1 on the left side. If it was positive, concatenate a 0 to the left side

And the procedure the other way around would look like 1. Disregard the MSB, convert the rest of the number into decimal. 2. If MSB was 1 put a negative sign in front. If MSB was 0, put a positive sign in front.

For example, a 2-bit number like 0b01 would be 1 in decimal, but 0b11 is -1.

Now let's analyze this number system with the three questions:

Question 1: How many unique values are represented by sign-magnitude? Well it might seem like there are $2^n$ possible values, but notice that the decimal number $0$ has two representations. In 8-bit, $0b0000\;0000$ and $0b1000\;0000$. So in all, given an n-bit number, there are $2^n - 1$ unique values. That is alright, but doesn't use all the bits to the fullest extent.

Question 2: What is the range? The highest value we can represent in 8-bit is $0b0111\;1111$, and the lowest is $0b1111\;1111$. In general, we can represent numbers from $[-2^{n-1}, 2^{n-1}]$.

Question 3: How easy is it to do math with? It's alright. You'll have to tell the computer extra instructions to do operations with negative numbers like $20 - 40 = -20$ where if the second number is greater than the first, you make it negative, etc. It's not great, but it feels pretty good.

Two's Complement Representation¶

In this representation, we can consider negative numbers in a creative way: let's encode the most significant bit (MSB) to be some negative and the rest of the numbers positive. For example, in 4-bit systems, $0b1000$ is just $-8$. The way I can see this is that the MSB is a 1, and if a 1 were in that spot regularly, it would be $8$, but since it is MSB, it is the negative of it. Then for numbers like $0b1100$, we would see that it is $-8 + 4 = -4$, and for $0b1110$, it would be $-8 + 4 + 2 = -2$. Here is a general rule for Two's Complement: for a n-bit number with bits $d_nd_{n-1}\dots d_1d_0$, two's complement says that the value is $$ \begin{align} -d_{n-1} * 2^{n-1} + d_{n-2}2^{n-2} + \cdots d_1 * 2^1 + d_0 * 2^0 \end{align*} $$ Through this, we see that only the MSB can encode the negative part, along with some size based on what is defined to be the MSB.

For example, in 8-bit systems, the binary number $0b1000\;1011$ in two's complement representation is $-2^7 + 2^3 + 2^1 + 2^0 = -128 + 8 + 2 + 1 = -117$.

This way of figuring out the value is a bit annoying if you try out a couple of examples, you have to work with negative numbers and adding them with positive numbers. There is actually a better way of finding the value. No matter what the number is, you can find the two's complement of that binary number, and the complement is just multiplying by $-1$. That rule, you'll know well: $\(\text{Flip the bits and add 1}$\) So, given a negative number, you can find the two's complement (the positive number) and then you know that the number is just the negative of that number. The same example above gives

$0b1000\;1011 \rightarrow 0b0111\;0100 + 1 = 0b0111\;0101 = 2^6 + 2^5 + 2^4 + 2^2 = 64 + 32 + 16 + 4 + 1 = 117$, so it represents $-117$.

This rule also works the other way. Here a positive number in 8-bit, two's complement: $0b0001\;1010$. If I wanted to find the negative value associated with it, it is simply $0b1110\;0101 + 1 = 0b1110\;0110$.

Again, let's analyze this number system:

Question 1: Unique values. We can actually use all the $2^n$ unique values, no binary number represents two different numbers in two's complement

Question 2: Range. The most negative number is $0b1000\dots$. and the most positive number is $0b0111\dots$. That means the range is $[-2^{n-1}, 2^{n-1} - 1]$. Notice the minus 1 at the end of the positive side, while the end of the negative side doesn't have that.

Question 3: Math? Let's see. In 4-bit, two's complement, a negative number plus a positive number is always the trickiest example to come up with: $0b1010 + 0b0111$. In decimal, it is $-6 + 7 = 1$. In binary, let's naively add them together: $0b1010 + 0b0111 = 0b0001$. One thing to notice is that we overflowed to the fifth bit, but since we are only adding two 4-bit numbers together, we need to disregard that carry bit at the end, but we do get the correct value at the end. This is true for all two's complement arithmetic. This means arithmetic with two's complement is just the simple binary addition, unlike how in sign-magnitude we need extra instructions to determine sign.

Two's Complement Hex¶

Only the MSB encodes negative information. In hex, it is not the symbol that encodes the negative information. Two's complement hex is just binary two's complement once you convert it into binary. It is not the most significant hex that encodes the negative information, only the most significant bit of the hex that encodes it. Therefore, a hex number like $0xFFFF\;FFFA$ is $0x1111\;1111\;1111\;1111\;1111\;1111\;1111\;1010$, which has the decimal value

\[ \begin{align*} 0b0000\;0000\;0000\;0000\;0000\;&0000\;0000\;0101 + 1 \\\qquad\qquad &= 0b0000\;0000\;0000\;0000\;0000\;0000\;0000\;0110 \\&= 6 \rightarrow -6 \end{align*} \]

Bias Representation¶

So far, we have discussed number systems that are somewhat centered around 0. But what happens if we wanted to represent numbers such as the temperature in Kelvin in the world around us, where $0$ represent something that we probably won't see in our lifetime? This is where bias representation comes in. To write a number in bias representation, we must know what the bias is. Let's denote the bias to be $B$.