Week 0 · Lesson 1
C and pointers
Every compiler in this course ends by printing C. To read that C, you need one picture in your head: memory is a long row of numbered bytes, and a pointer is just one of those numbers.
The course tools are written in Python 3, so install Python 3 first. The C exercises need a C compiler on your PATH: clang or gcc. On Windows the easiest route is a MinGW-w64 build (from WinLibs, or through MSYS2). The LLVM installer alone can't link programs unless Visual Studio's build tools are also installed. Check with gcc --version or clang --version in a new terminal.
Memory is a row of bytes
Your program's memory is one huge array of bytes. Each byte has an address, which is just its position in the row. A variable is a name for a few consecutive bytes. An int is usually 4 bytes, a char is 1, a double is 8, and on a 64-bit machine a pointer is 8.
A pointer is a variable that holds an address. &x means "the address of x". *p means "the value at the address stored in p". That's it. Everything else is bookkeeping about how many bytes each thing takes.
Arrays are a base address plus an offset
An array int a[4] is 4 ints laid out back to back, 16 bytes in total. If a[0] lives at address 0x1000, then a[1] is at 0x1004, a[2] at 0x1008, and so on. (0x means the number is written in hexadecimal: base 16, with digits 0 to 9 then a to f. So 0x1004 is 4 more than 0x1000, and 0x100c is 12 more.) In general:
address of a[i] = base + i * sizeof(element)This formula is the most important line in the whole course. By week 5 you'll be generating code that turns a 4D tensor index into exactly this: one base address plus one computed offset.
Step through the snippet below. Watch what p + 1 does: it moves 4 bytes, not 1, because C scales pointer arithmetic by the size of what p points to.
p[i] is *(p + i)
Indexing is defined as pointer arithmetic. p[2] is exactly *(p + 2): add 2 elements to the address, then read. That's why C has no bounds checking. It computes an address and reads whatever is there. In week 2 your compiler will bounds check every load and store, because C won't.
sizeof
sizeof gives a size in bytes, computed at compile time. sizeof(int) is 4 on every machine you'll use. For int a[4], sizeof(a) is 16. But pass a to a function and it "decays" into a plain int *, and inside that function sizeof gives 8, the size of a pointer. The array's length is gone. That's why every function your compiler generates (we'll call those generated functions kernels) will pass sizes separately, or bake them in as constants.
Enough C for the exercises on this page:
int f(int a) { // a function: return type, name, parameters
int t = 0; // a local variable
for (int i = 0; i < a; i++) // a loop: start; keep going while true; step
t += i; // t = t + i
return t; // the function's result
}
printf("%d\n", x); // prints the int x and a newline
(uint32_t)a // a cast: converts a to an unsigned 32-bit intSum an array with a pointer
Write int sum(const int *p, int n): add up the n ints starting at address p and return the total. Use p[i], or move p itself with p++. Both are the same address math.
When n is 0, p may be NULL. Don't read through it.
Why does const int *p say const?
const int *p is a pointer to ints you promise not to write through. The pointer itself can still move, so p++ is fine. Generated kernels mark their input buffers this way so the C compiler knows they aren't modified.
Integers are 32 bits of two's complement
An int32 has 32 bits. Read as an unsigned number they go from 0 to 232−1. Two's complement reads the top bit as worth −231 instead of +231. So the range is −2,147,483,648 (INT_MIN) to 2,147,483,647 (INT_MAX), and -1 is all ones, 0xffffffff.
Check that last one: with all 32 bits set, the top bit is worth −2,147,483,648 and the other 31 ones add up to +2,147,483,647. Together that's −1.
Type a number to see its bits. The top bit (the sign bit) is underlined.
If you add 1 to INT_MAX and keep only the low 32 bits, you get INT_MIN. That's called wrapping. The hardware does it, and the language you'll compile in this course defines add and mul to wrap exactly like that.
In C, signed overflow (INT_MAX + 1 on an int) is undefined behavior. The compiler is allowed to assume it never happens, and optimizers really do use that. Unsigned arithmetic (uint32_t) is defined to wrap. When your compiler prints C for a wrapping i32 add (i32 is the course's 32-bit integer type), it'll need to cast to unsigned, add, and cast back, or pass a flag like -fwrapv. That last cast back is "implementation-defined": the C standard lets each compiler choose what happens, and every compiler you'll use wraps. Keep this in your back pocket for week 2.
Code quiz: add with wraparound, no UB
Write int32_t wrap_add(int32_t a, int32_t b) returning a + b wrapped to 32 bits, so wrap_add(INT_MAX, 1) == INT_MIN. Don't add two signed ints directly: do the add in uint32_t, where wrapping is defined, then convert back. A cast is written (uint32_t)a, and int32_t and uint32_t come from <stdint.h>, which the exercise already includes for you.
Integer division truncates toward zero
Since C99, / on integers rounds toward zero, and % is defined so that (a / b) * b + a % b == a. That means the remainder takes the sign of the left operand:
| expression | C result | why |
|---|---|---|
7 / 2 | 3 | 3.5 rounds toward zero |
-7 / 2 | -3 | −3.5 rounds toward zero, not down to −4 |
-7 % 2 | -1 | −3 × 2 + (−1) = −7 |
7 % -2 | 1 | −3 × −2 + 1 = 7 |
INT_MIN / -1 | undefined | the true quotient, 2147483648, doesn't fit in an int |
x / 0 | undefined | traps on x86; ARM64 quietly returns 0 |
Python's // rounds down (-7 // 2 == -4) and its % follows the right operand's sign (-7 % 2 == 1). Lots of tutorials are written in Python. The course's div and mod follow C.
Code quiz: Python's // from C's /
Write int floor_div(int a, int b) that rounds down like Python: floor_div(-7, 2) == -4. Start from C's truncating a / b and fix it up. When does truncation differ from flooring? Only when there's a remainder and the signs of a and b differ. b is never 0.
Check yourself
On the 64-bit machines this course targets, what is sizeof(int)?
Going from 32-bit to 64-bit machines doubled the size of pointers. Did it change int?
4 bytes, 32 bits. Pointers are 8 bytes on a 64-bit machine, but int stayed at 4.
int a[4] starts at address 0x1000. What's the address of a[3]? (hex)
Each int is 4 bytes, so element k starts at base + 4k.
3 × 4 is 12. What is 12 in hex?
base + 3 × 4 = 0x1000 + 12 = 0x100c.
Predict the output.
int a[4] = {10, 20, 30, 40};
int *p = a + 1;
printf("%d\n", p[1]);p starts at a + 1, which is the address of a[1]. Then p[1] moves one more element.
p points at a[1], so p[1] is *(a + 1 + 1), which is a[2] = 30.
Predict the output of printf("%d", -7 / 2); in C.
The exact answer is -3.5. Which way does C round: down, or toward zero?
C truncates toward zero. −3.5 becomes −3.
Predict the output of printf("%d", -7 % 2); in C.
C guarantees (a / b) * b + a % b == a. You know -7 / 2 from the previous quiz.
Since -7 / 2 == -3, the remainder must satisfy −3 × 2 + r = −7, so r = −1.
What does the C standard say INT_MAX + 1 evaluates to, for a plain int?
The section above has a trap box about this. Think about what the C standard promises, not what the hardware does.
Your hardware would wrap to INT_MIN, but C promises nothing, and optimizers rely on that. Unsigned types are the ones defined to wrap.
What is -1 as a 32-bit two's complement number, in hex?
In two's complement, -1 is the number that becomes 0 when you add 1.
Adding 1 to 0xffffffff carries out of all 32 bits.
All 32 bits set. Adding 1 to it wraps to 0, which is exactly what −1 + 1 should give.
A function is declared void f(int a[4]). Inside f, what is sizeof(a) on a 64-bit machine?
Can C pass a whole array to a function by value? What does an array turn into when it's passed?
Array parameters decay to pointers. The [4] in the signature is decoration, and the length is lost.