Computer Architecture

Last Modified: 2/12/2025

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

1 Bit, Bytes & 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.

Conversion between bases

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)$.

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)$.

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}$

1.2.5 Bias Notation

Properties

• Idea: Just like unsigned, but shifted on the number line.
• Smallest number: $\texttt{0b0000...000}$ represents $\text{bias}$.
• Largest number: $\texttt{0b0111...111}$ represents $+\left(2^N - 1 + \text{bias}\right)$.

1.2.6 Sign Extension

For binary representation, leftmost bit is the most significant bit (MSB), and rightmost bit is the least significant bit (LSB).

• Idea: Want to represent the same number using more bits than before. It’s easy for positive numbers (add leading 0’s), but more complicated for negative numbers.
• Sign and magnitude: Add 0’s after the sign bit.
• One’s/Two’s complement: Copy MSB.

Example

• Sign and magnitude: $\texttt{0b1101}=\texttt{0b1000 0101}$
• One’s complement: $\texttt{0b1100}=\texttt{0b1111 1100}$

2 C Introduction

2.1 Variable C Types

2.2 Addresses & Pointers

A computer memory location has an address and holds a content. A pointer variable (or pointer in short) is basically the same as the other variables, but it stores a memory address.

The size of the address (and of course, the pointer) depends on the architecture of the computer. For example, in a 32-bit system, the size of the pointer is 4 bytes, while in a 64-bit system, the size of the pointer is 8 bytes.

Example

1
int *p; // declaration
2
int x = 3;
3

4
p = &x; // assign the address of x to p
5

6
printf("%u %d\n", p, *p);
7
// Output: 0xc7977ff934 3
8

9
*p = 5; // changes value of x to 5
10

11
void *p1; // can be used to store any address

2.3 Arrays

Declaration & Initialization:

1
int arr[5];
2
int arr1[] = {1, 2, 3, 4, 5};
3
printf("%d\n", arr1[2]);

A better pattern: single source of truth!

1
int ARRAY_SIZE = 5;
2
int arr[ARRAY_SIZE];
3
for (int i = 0; i < ARRAY_SIZE; i++) {
4
    arr[i] = i;
5
}

2.4 Strings

In C language, strings are stored in an array of characters. The end of the string is marked by a special character, the null character \0.

1
char str[] = "Hello, World!";
2
char str1[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
3
char str2[6] = "Hello";

Here are some commonly-used string functions defined in the string.h library:

1. size_t strlen(const char * str): Returns the length of the string (not including the null terminator).
2. char * strcpy ( char * destination, const char * source ): Copies the C string pointed by source into the array pointed by destination, including the terminating null character (and stopping at that point).
3. char * strncpy ( char * destination, const char * source, size_t num ): Copies the first num characters of source to destination. If the end of the source C string (which is signaled by a null-character) is found before num characters have been copied, destination is padded with zeros until a total of num characters have been written to it.
4. int strcmp ( const char * str1, const char * str2 );: Compares the C string str1 to the C string str2, return 0 if str1 and str2 are identical.
5. int strncmp ( const char * str1, const char * str2, size_t num ): Compares up to num characters of the C string str1 to those of the C string str2.
6. char * strcat ( char * destination, const char * source ): Appends a copy of the source string to the destination string. The terminating null character in destination is overwritten by the first character of source, and a null-character is included at the end of the new string formed by the concatenation of both in destination.
7. char * strncat ( char * destination, const char * source, size_t num ): Appends the first num characters of source to destination, plus a terminating null-character.