Computer Architecture

Last Modified: 1/17/2025

In this part, we will explore computer architecture, both x86-64 and RISC-V architecture.

1 Number Representation

1.1 Number Base

In computer science, There are three commonly-used number bases: binary, decimal & hexadecimal.

1. Binary (base 2)
   • Symbols: 0, 1
   • Notation: $101011_2=\texttt{0b101011}$
   • Converting numbers to base 2 lets us represent numbers as bits!
2. Decimal (base 10)
   • Symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
   • Notation: $9472_{10}=9472$
   • Understandable by humans, used in our daily life.
3. Hexadecimal (base 16)
   • Symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
   • Notation: $2A5D_{16}=\texttt{0x22400}$
   • A convenient shorthand for writing long sequences of bits.

1. Convert from other bases to base-10: write out power of bases.

   For example, $AC2_{16}=(10 \times 16^2)+(12 \times 16^1)+(2 \times 16^0)=2754$

2. Convert from base-10 to other bases: Use the “leftover algorthm”

   For example, convert $73_{10}$ to base-4. For base-4, the powers of base include 256, 64, 16, 4, 1.

   • How many multiples of $64$ fit in $73$? $73 - 64 = 9$ left over.
   • How many multiples of $16$ fit in $9$? Still $9$ left over.
   • How many multiples of $4$ fit in $9$? $9 - 2 \times 4 = 1$ left over.
   • How many multiples of $1$ fit in $1$? $1 - 1 = 0$, which means we are done!

   Therefore, $73_{10}=1021_4$.

When converting between different bases, you can refer to the following table below.

1.2 Integer Representation

1.2.1 Unsigned Integers

Properties

• Idea: Simply convert decimal to binary, cCan represent $2^N$ different numbers!
• Smallest number: $\texttt{0b 0000...000}$ represents $0$.
• Largest number: $\texttt{0b 1111...111}$ represents $2^N-1$.

Conclusion

1.2.2 Signed Integers

Properties

• Idea: Use the left-most bit to indicate if the number is positive (0) or negative (1). This is called sign-magnitude representation.
• Smallest number: $\texttt{0b1111...111}$ represents $-\left(2^{N - 1} - 1\right)$.
• Largest number: $\texttt{0b0111...111}$ represents $+\left(2^{N - 1} - 1\right)$.

Note

If we count upwards in base-2, the resulting numbers increase, then they start decreasing!

Plus, there are two ways of representing zero: $\texttt{0b100...00}$ & $\texttt{0b000..00}$.

1.2.3 One’s Complement

Properties

• Idea: If the number is negative, flip the bits. For example, $+7$ is $\texttt{0b00111}$, so $-7$ is $\texttt{0b11000}$. Left-most bit acts like a sign bit. If it’s 1, someone flipped the bits, so number must be negative.
• Smallest number: $\texttt{0b1000...000}$ represents $-\left(2^{N - 1} - 1\right)$.
• Largest number: $\texttt{0b0111...111}$ represents $+\left(2^{N - 1} - 1\right)$.

Note

If we count upwards in base-2, the resulting numbers are always increasing.

There are two ways of representing zero: $\texttt{0b111...11}$ & $\texttt{0b000..00}$.

1.2.4 Two’s Complement

Properties

• Idea: If the number is negative, flip the bits, and add one (because we shift to avoid double-zero). Because of overflow, addition behaves like modular arithmetic (For example, $11$ and $-5$ are the same in $\bmod$ land: $11 \equiv -5 \pmod{16}$).
• Smallest number: $\texttt{0b1000...000}$ represents $-2^{N - 1}$.
• Largest number: $\texttt{0b0111...111}$ represents $+\left(2^{N - 1} - 1\right)$.

Conversion between two’s complement and signed integer

1. Two’s Complement -> Signed Integer

   • If left-most digit is 0: Read it as unsigned
   • If left-most digit is 1:
     • Flip the bits, and add 1
     • Convert to base-10, and stick a negative sign in front

   Example: What is $\texttt{0b1110 1100}$ in decimal?

   • Flip the bits: $\texttt{0b0001 0011}$
   • Add one: $\texttt{0b0001 0100}$
   • In base-10: $-20$

2. Signed Integer -> Two’s Complement

   • If number is positive: Just convert it to base-2
   • If number is negative:
     • Pretend it’s unsigned, and convert to base-2
     • Flip the bits, and add 1

   Example: What is $-20$ in two’s complement binary?

   • In base-2: $\texttt{0b0001 0100}$
   • Flip the bits: $\texttt{0b1110 1011}$
   • Add one: $\texttt{0b1110 1100}$