Pointer Arithmetic
Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.
Pointer Basics
Pointers are one of the first things that are used ubiquitously in C, while almost not existing in Python! Consequently, the ability to use pointers is one of the reasons why we want to teach you C in this class. Pointers allow us programmers to work much closer to how the computer actually stores and manipulates data. This may all sound like jargon right now, so let's break this down!What is a pointer? To understand pointers we first have to understand how computers store data in memory. In this class, we will use a simplified model of memory. Consider all memory to be made up of consecutive “blocks”, almost like an infinite array. Each block can hold 8 binary values (8 bits), or 1 byte of information. We think of having a very large quantity of these blocks in some sequential ordering, again very analogous to how we visualize python arrays. To let the computer interact with this data, each block needs to have a label. We call this label an address, and usually write it in hexadecimal. These blocks are labeled sequentially, so if 0x10 (or 16 in decimal) is the first block,then 0x11 would be the second block (17 in decimal). In C, we store this address to data in a pointer! We call it a pointer because in essence, this pointer is pointing towards data we would like to reference.
Declaring variables and pointers. In python we do not use pointers. Therefore we can use syntax like:
classNumber = 60004
to create a variable. What python does behind the scenes, however, is allocate blocks of memory to hold this number, and then create a reference to the address in which that data is stored. The same thing happens in C. When we declare an integer variable in C:
int classNumber = 60004;
C also allocates memory for this variable, and then makes a reference to the address of this variable in memory. However, in C, we can actually access this reference to memory by creating a pointer to our variable.
We can declare a pointer to this value by using the following syntax:
int* classNumberPointer = &classNumber;
Let us break down this syntax. int* classNumberPointer declares an object of type Integer pointer. This pointer is then assigned the value &classNumber which uses the address operator of “&” to allow access to the memory address of classNumber.
We can also go the other way by using a pointer to reference the value it points to. Assume that we have an integer pointer classNumberPointer, and we want to get the value it points to (60004). To do this, we again use the “*” operator, in this case called the dereference operator.
*classNumberPointer /* equals 60004 */
Now it’s your turn to use some pointers!
x?
Write a function that takes in an integer pointer and returns the value pointed to by the pointer.
Pointers to different types
So far we have seen pointers to integers. However, we can make pointers to any type of object in C. Different types of variables take up different amounts of memory. Integers take up 4 bytes (i.e., 4 blocks of data), chars take up 1 byte, floats take up 4 bytes, and doubles take up 8 bytes. Dereferencing pointers of a certain type will always return a value of that type. So, for example, dereferencing an integer pointer will always return an integer, whereas dereferencing a char pointer will return a char.
Pointers to Arrays: Arrays in C are pointers to the type of element held by the array. Consider the array:
int x[4] = {1,2,3,4};
The statement above declares an array of 4 integers. x is a pointer to integer. *x gives access to the first element of the array, as does x[0]. This is because x actually points to the first element of the array (in other words, the "address" of x is = &x[0]). x[1] gives access to the next element of the array. Note that the address of x[1], &x[1], however is ((int)(&x[0])) + 4. This is because x is an array of integers and each integer takes up 4 bytes of memory. (In C, you could write &x[0] + 1 to access the address of x[1], since C knows &x[0] is int* and will know to move 4 bytes.)
Another way to get the address of x[1] is to increment x itself by 1, x = x + 1. If you increment x by 1 and then dereference *x, you will get the next element of the array. Even though the address of x[1] is 4 bytes away, C knows that incrementing an integer pointer is equivalent to adding 4 to it.
Analogously, if you were to declare a char array:
char y[5] = {'a', 'b', 'c', 'd', 'e'};
*y and y[0] would both return 'a'. If you then increment y by 1 the resulting address will be ((int)(&y[0]))+1 because each character only takes up one byte of memory.
Consider the following code:
int* x = (int*) 0;
x=x+7;
x?
Now consider this code:
char* x = (char*) 0;
x=x+7;
x?
Given the following array declaration:
int[10] values= {0,5,10,15,20,25,30,35,40,45};
We can access element 2 of values by simple indexing i.e, values[2] which would have a value of 10.
However, “values” is not actually an array "object" in C; there's no such thing. It is is more accurately though of as a pointer to a continuous block of memory allocated to the values array.
*(values + 3)?
*(&values[7] - 2)?
*(values+2)+values[2]?
Array Pointers
Consider the following three array declarations:
char letters[] = {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’};
int values[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
double real_numbers[] = {0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9};
Assume that the address of letters is 0x10, values is 0x100, and real_numbers is 0x1000. What is the address of the fourth element (i.e. the element at index 3) in each array?
letters (addr of
letters[3])? 0x
values (addr of values[3])
? 0x
real_numbers (addr of
real_numbers[3])? 0x
Merge sort
Now, it’s your turn to use pointers. One of the most widely used sorting algorithms is merge sort, which you will learn about later in 6.006 or other classes. Part of merge sort requires us to be able to take two already sorted arrays and then merge them into another sorted array. The key idea is that we keep two pointers, one pointer to the head of each sorted list. We then compare the values of the items these two pointers point towards. Whichever value is lower between these two values gets added to the merged list first. Then we increment the pointer from the list that the smaller value comes from in order to point to the next element in that sorted list.
Write a function that takes in three pointers to integer arrays, one for the destination array and two for the two sorted arrays you want to merge sort. Assume that the length of each input array is 10.