CS61C-1 Introduction and C

Notes from working through the CS61C course, following the Spring 2025 offering of CS61C: Computer Architecture(Machine Structures).
This post covers the course Introduction and the basics of the C language. Lecture 1-7, Discussion 1-2.

Thinking about Machine Structures

Great Ideas in Computer Architecture

Abstraction (Layers of Representation/Interpretation)
Mooreʼs Law
Principle of Locality/Memory Hierarchy
Parallelism
Performance Measurement & Improvement
Dependability via Redundancy

Number representation

Bias Encoding

Suppose we have a data value x. When storing it: stored value = x - bias (the result is stored as an unsigned number); when reading it back: actual value = (stored unsigned number) + bias.

In an N-bit representation, the bias is usually chosen as

$- (2^{N-1} - 1)$

Example: N = 4, bias = -7
For 0, the stored value is:

$0 - (-7) = 7$

When read back, the actual value is:

$7 + (-7) = 0$

Intro to C

Since I have extensive C++ development experience, I’ll focus on the differences between C and C++.

Compile

1	gcc hello.c -o hello

Header file: #include <stdio.h>

The printf and scanf functions

Format arguments:

%d: integer
%f: floating-point number
%c: character
%s: string
%p: pointer
%u: unsigned integer
%g: automatically picks a suitable representation

scanf needs the address-of operator &, because scanf has to store the input value into the variable.

#include <stdio.h>

int main() {
    int a;
    float b;
    char c;
    char str[100];

    // 输入整数
    printf("请输入一个整数: ");
    scanf("%d", &a);

    // 输入浮点数
    printf("请输入一个浮点数: ");
    scanf("%f", &b);

    // 输入字符
    printf("请输入一个字符: ");
    scanf(" %c", &c); // 注意前面的空格，跳过前面的空白字符

    // 输入字符串
    printf("请输入一个字符串: ");
    scanf("%s", str); // 不需要取地址符，因为数组名即为地址

    // 输出结果
    printf("您输入的整数是: %d\n", a);
    printf("您输入的浮点数是: %.2f\n", b);
    printf("您输入的字符是: %c\n", c);
    printf("您输入的字符串是: %s\n", str);

    return 0;
}

String handling

<string.h> is a header file in the C standard library that provides a set of functions for working with strings. Here is a closer look at some of the commonly used ones:

strlen: compute the length of a string
strcpy: copy a string
strcat: concatenate strings
strcmp: compare strings
strchr: find a character
strstr: find a substring
strncpy: copy a string up to a specified length

#include <stdio.h>
#include <string.h>

int main() 
{
    char str1[] = "Hello, World!";
    char str2[20];  

    // 计算字符串长度
    int len = strlen(str1);
    printf("字符串长度: %d\n", len);

    // 复制字符串
    strcpy(str2, str1);
    printf("复制后的字符串: %s\n", str2);   

    // 连接字符串
    strcat(str1, " Welcome!");
    printf("连接后的字符串: %s\n", str1);

    // 比较字符串
    int cmp = strcmp(str1, str2);
    if (cmp == 0) 
    {
        printf("两个字符串相等\n");
    } 
    else if (cmp < 0) 
    {
        printf("str1 小于 str2\n");
    } 
    else 
    {    
        printf("str1 大于 str2\n");
    }

    // 查找字符
    char ch = 'o';
    char *pos = strchr(str1, ch);
    if (pos != NULL) 
    {      
        printf("字符 %c 的位置: %d\n", ch, pos - str1);
    } 
    else 
    {
        printf("字符 %c 未找到\n", ch);
    }

    return 0;
}

results:

字符串长度: 13
复制后的字符串: Hello, World!
连接后的字符串: Hello, World! Welcome!
两个字符串相等
字符 o 的位置: 4

Classic line: “C gives you a lot of extra rope, donʼt hang yourself with it!ˮ

malloc, free and realloc

#include <stdio.h>
#include <stdlib.h>

int main() 
{    
// 现代C语言中，malloc 返回的是 void* 类型，但编译器会进行隐式转换
    int *p = malloc(sizeof(int));
    int *arr = malloc(sizeof(int) * 10);
    int *arr2 = realloc(arr, sizeof(int) * 20);
    *p = 10;
    for (int i = 0; i < 10; i++) 
    {
        arr[i] = i;
    }
    printf("%d\n", *p);
    free(p);
    free(arr);
    free(arr2);
    return 0;
}

K&R Malloc/Free Implementation

Memory block structure: every memory block is preceded by a header containing two fields. One is the size of the block, recording how many bytes the block holds; the other is a pointer to the next block. In allocated blocks the pointer field is unused, while all free blocks are linked together through this pointer field into a circular linked list, which makes memory management convenient.
malloc() implementation: malloc() allocates memory from the heap. It searches the free list for a block large enough to satisfy the request. If a suitable block is found, it is removed from the free list and split if necessary (when the requested size is smaller than the block found), and a pointer to the start of the allocated memory is returned. If no block on the free list is large enough, malloc() requests more memory from the operating system. If the memory provided by the operating system still cannot satisfy the request, malloc() returns NULL, indicating that the allocation failed.
free() implementation: free() releases heap memory that is no longer in use. When free() is called, it first checks whether the blocks adjacent to the one being freed are also free. If so, free() coalesces these adjacent free blocks into a single larger free block, which reduces fragmentation and improves memory utilization. If the adjacent blocks are all in use, the freed block is simply added to the free list. This way, the block can be handed out again by a later call to malloc().
Design goals: the main goal of the K&R implementation is to make malloc() and free() run efficiently while keeping memory overhead low and avoiding fragmentation. Fragmentation means that although the system has plenty of free memory, it exists as many small, non-contiguous blocks, so large allocation requests cannot be satisfied. Through sensible block management and a coalescing strategy, the K&R implementation mitigates these problems to a degree and gives C programs a reasonably effective memory management scheme.

Function Pointers

#include <stdio.h>

int square(int x) 
{
    return x * x;
}

int cube(int x) 
{
    return x * x * x;
}

int main() 
{
    // 声明一个函数指针，指向一个接收int返回int的函数
    int (*math_func)(int);
    
    // 将函数指针指向square函数
    math_func = square;
    printf("平方结果: %d\n", math_func(5));  // 输出: 25
    
    // 将函数指针指向cube函数
    math_func = cube;
    printf("立方结果: %d\n", math_func(5));  // 输出: 125
    
    return 0;
}

Generic Functions

A generic pointer (void *) cannot be used with the dereference operator, because dereferencing a pointer requires the number of bytes to access to be known at compile time.

#include <stdio.h>
#include <string.h>

// 泛型swap函数：交换任意类型的两个元素
void swap(void *a, void *b, size_t size) 
{
    char temp[size];  // 创建临时缓冲区
    memcpy(temp, a, size);     // 将a的内容复制到临时缓冲区
    memcpy(a, b, size);        // 将b的内容复制到a
    memcpy(b, temp, size);     // 将临时缓冲区的内容复制到b
}

int main() {
    // 交换整数
    int x = 5, y = 10;
    printf("交换前: x = %d, y = %d\n", x, y);
    swap(&x, &y, sizeof(int));
    printf("交换后: x = %d, y = %d\n", x, y);

    // 交换浮点数
    double d1 = 3.14, d2 = 2.718;
    printf("交换前: d1 = %f, d2 = %f\n", d1, d2);
    swap(&d1, &d2, sizeof(double));
    printf("交换后: d1 = %f, d2 = %f\n", d1, d2);

    return 0;
}

To do pointer arithmetic in generic code, first cast the void * pointer to a char * pointer. Because char occupies 1 byte on every architecture, pointer arithmetic after the cast is in units of bytes, which guarantees the arithmetic proceeds byte by byte.

Example:

In a swap_ends function that swaps the first and last elements of a generic array, to compute the address of the last element, first convert the void * pointer arr (which points to the start of the array) to char *, then compute it with the formula (char * ) arr + (nelems - 1)* nbytes, where nelems is the number of elements in the array and nbytes is the size of each element in bytes.

Floating Point Representation

Review of number representation

Computers represent numbers in binary; N bits can represent $2^N$ distinct values. Unsigned integers range from 0 to $2^N - 1$ , and signed integers (two’s complement) range over $-2^{N - 1} \text{ to } 2^{N - 1} - 1$ .

Fixed-point representation

Fixed-point is a number representation in which the position of the radix point is fixed. By fixing the position of the binary point in advance, both an integer part and a fractional part can be represented.

For example, in an 8-bit fixed-point representation, if we designate the first 4 bits as the integer part and the last 4 bits as the fractional part:

The number 5.5 is represented as: 0101.1000
- Integer part 5 = 0101₂
- Fractional part 0.5 = 0.5 × 2⁴ = 8 = 1000₂
The number 3.25 is represented as: 0011.0100
- Integer part 3 = 0011₂
- Fractional part 0.25 = 0.25 × 2⁴ = 4 = 0100₂

The advantage of fixed-point is that arithmetic is simple; the drawback is the limited range:

In the 8-bit system above, the integer part ranges from 0-15
The precision of the fractional part is fixed at 1/16 (0.0625)

Floating-point representation

Floating point separates the binary point from the significand, making efficient use of a limited number of bits to represent more numbers. The IEEE 754 standard specifies that a single-precision float is 32 bits: 1 sign bit, 8 exponent bits, and 23 significand bits. The significand has an implicit leading 1, and the exponent uses a bias encoding with a bias of 127.

Properties of floating-point arithmetic: floating-point addition is not associative; different evaluation orders can give different results, because floating-point representation is approximate and a larger exponent means a larger step size. Floating-point arithmetic involves rounding, and IEEE 754 has several rounding modes, such as rounding toward +∞ or -∞, truncation, and rounding to even.
Special floating-point values: these include zero (±0), infinity (±∞), and not-a-number (NaN). An exponent of 0 with an all-zero significand represents ±0; an exponent of 0 with a nonzero significand represents a denormalized number; an exponent of 255 with an all-zero significand represents ±∞; an exponent of 255 with a nonzero significand represents NaN, which is used to handle overflow, underflow, invalid operations, and so on.
Floating-point formats of different precision: compared with single precision, double precision (64 bits) uses an exponent bias of 1023 and can represent numbers with a wider range and higher precision. There are also other formats such as half precision (16 bits) and quad precision (128 bits), each with its own use cases; for example, half precision is used in machine learning to speed up computation.

Discussion 1

Discussion 1 Solutions

Discussion 2

Discussion 2 Solutions

Translated from the Chinese original.