1.1 Decimal, Binary, and Hexadecmial Number Systems¶

This note talks about how to convert between number systems, paying particular focus on the decimal, binary, and hexademical number systems. Get back to toc CS61C or 1. Number Representation

Decimal Number System¶

The system you choose to count is kind of arbitrary. Like, we have 10 symbols in our counting, where once we reach the last symbol, we create a new place value that increses by one value. But the amount of symbols we have is arbitrary. It is likely chosen because we have 10 fingers on both our hands, and thus have 10 symbols, but I could choose a number system that is 12 (called the dozenal number system) and can do math that way.

Nevertheless, it is good to frame our decimal number system in terms of how we will analyze other number systems. Namely, let's talk about place value and expanded notation.

A number like 123 can be broken down into place values: we have 3 ones, 2 tens, and 1 hundreds. We can therefore write it as $1*10^2 + 2 * 10^1 + 3 * 10^0$ Where we can read it from right to left, increasing the power of ten by 1 whenever we go up a place value.

With 3 locations to place a number we have a total of $10^3$ unique values, however, we can only count from $[0, 10^3 - 1]$. More generally, given $n$ locations to write a number, we have $10^n$ unique values, and our range is from $[0, 10^n - 1]$.

That is really all there is to our number system, some sequence of numbers based on how many symbols we have, a way to write bigger numbers with place values. We can also indicate how many possible values we might have, as well as the range we span across.

Binary Number System¶

The binary number system is no different, except we only have 2 symbols in our counting. A binary digit (also called a bit) is one such symbol. We can chain together 8 bits into a byte. Starting from $0$ with eight bits, we count up just like we do in decimal: once we run out of symbols, increment the next place value by 1, and put all previous place values back to 0. With 4 bits, the sequence may start like $0b0000$, $0b0001$, $0b0010$, $0b0011$, $0b0100$, $0b0101, 0b0110$, $0b0111$, $0b1000$, Where these are the numbers from 0 to 8. One thing to note is that I will denote binary numbers with a $0b$ prefix, but decimal numbers I will write them without any prefix.

Similarly given a certain number a bits, such as $4$, there are only $2^4$ unique values that can be represented, and since we start with $0$, we can count up to $2^4 - 1 = 15$. More generally, give an $n$ bit number in unsigned represenation (we will learn other representations in 1.2 Signed Representations), we can uniquely represent $2^n$ values, with range $[0, 2^n-1]$.

Again, just like decimal numbers, we can break down a binary number by looking at powers of 2. For example: $0b10101 = 1 * 2^4 + 0 * 2^3 + 1*2^2 + 0*2^1 + 1*2^0$.

Binary <-> Decimal¶

To switch from binary to decimal is actually quite simple. If you can break the binary number down just like how we did above, then compute the value, The number above yields $\(0b10101 = 1 * 2^4 + 0 * 2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 16 + 4 + 1 = 21$\)I would highly recommend remembering the first couple powers of 2, though you'll probably memorize it along the way since it is used so much in this course. I'd say up to $2048$ would be good enough, so you could represent numbers from $[0, 4096 - 1]$ easily (or equivalently write any 12 bit number).

$$ \begin{align} 2^0 = 1 && 2^1 = 2 && 2^2 = 4 && 2^3 = 8\ 2^4 = 16 && 2^5 = 32 && 2^6 = 64 && 2^7 = 128\ 2^8 = 256 && 2^9 = 512 && 2^{10} = 1024 && 2^{11} = 2048 \end{align} $$ Decimal to binary number involves a lot of subtracting, but here is a general procedure 1. Find the highest power of 2 that does not exceed the decimal number. 2. Subtract it by that value. At the same time, you know that the bit at that place value will contain a 1. Any power of 2 that you skip will have that bit place value be 0. 3. Continue this all the way until you reach $2^0 = 1$.

For example, writing $100$ in binary makes me do the following process:

100 - 64 = 36. 36 - 32 = 4, 4 - 4 = 0. I used bits at $2^6, 2^5, 2^2$, so the binary number is $0b1100100$. I can double check by ensuring $0b1100100 = 2^6 + 2^5 + 2^2 = 64 + 32 + 4 = 100$.

As you can see, knowing the powers of two helps you do these problems a bit faster than having to recall or write down the powers of two everytime. You will do this quite frequently, so I'd get used to the procedure while you can.

Binary to Hexadecmial¶

Hexadecimal is a number system that uses 16 symbols for counting (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F). To represent hex values, we place a $0x$ as a prefix, just like we do $0b$ for binary. It is actually easier to convert binary to hex and hex to binary than it is using the decimal system with conversions. Why? Let's notice the following fact.

Every group of 4 bits can be characterized by a single hex symbol. For example $0xC = 0b1100$, and $0xAB = 0b 1010\;1011$. I'd recommend you remember all the hex to binary conversions.

$$ \begin{align} 0x0 = 0b0000 && 0x1 = 0b0001 && 0x2 = 0b0010 && 0x3 = 0b0011\ 0x4 = 0b0100 && 0x5 = 0b0101 && 0x6 = 0b0110 && 0x7 = 0b0111\ 0x8 = 0b1000 && 0x9 = 0b1001 && 0xA = 0b1010 && 0xB = 0b1011\ 0xC = 0b1100 && 0xD = 0b1101 && 0xE = 0b1110 && 0xF = 0b1111 \end{align} $$ Just so you understand the importance of Hex and Binary conversions, Binary to Hex and vice versa conversions will be used on the following ways in the rest of this course: 1. When talking about the address of something in memory 2. Translating RISC-V code to 32-bit instructions 3. Debugging your CPU Project 4. Caching 5. Virtual Memory By the end of the course, you will hopefully be proficient in doing binary-hex conversions because you'll end up doing it so much.

So here is a quick example of doing such a conversion. You'll learn that that xor is a RISC-V instruction, and inputting something like xor t0, t1, t2 has the hex $0x007342B3$ Translate this into binary.

All I would do is just use the binary-hex translations for each hex character and concatenate all of them together. $\(0b 0000\;0000\;0111\;0011\;0100\;0010\;1011\;0011$\) Just to preview what is to come, $t0 = 0b00101, t1 = 0b00110, t2 = 0b00111$. You might see these segments hidden in the 32-bit number we just wrote out. All the other bits are meant to indicate that xor was the operation that was used.

Another example, translating $0b1110101010101111101011101$ to hex.

I would first separate them into groups of 4, like so $\(0b1\; 1101\; 0101\; 0101\; 1111\; 0101\; 1101$\) One thing to note is that we start the groupings from the right to left. Then convert all groups of 4 into its corresponding hex. The 1 at the beginning can be thought of as 1 with padded 0s at the front. Therefore, I get $$ 0x 1D55F5D $$

Hex <-> Decimal Conversions¶

The process is just the same for Binary <-> Decimal. From Hex to Decimal, represent each digit as a power of 16, but first convert each symbol into base 10. A number like $0xCF3$ is just $\(0xCF3 = 12 * 16^2 + 15*16^1 + 3 * 16^0$\) And you can do the same analysis from decimal to hex if you know your powers of 16 times some number. A number like $300$ would be like

$300 - 1 * 16^2 = 300 - 256 = 44. 44 - 2 * 16^2 = 44 - 32 = 12. 12 - 12 * 16^0 = 0$. The hex number is $0x12C$.

As you can see it is far easier to translate from decimal to hex and vice versa using the binary system as an intermediate step.