Recitation 2

Table of Contents

1) Two's Complement

In two's complement the MSB represents a negative value and all other bits represent a positive value. The magnitude of each bit is 2^{bit}.

So 0b0100 = 2^2 = 4 just like unsigned binary.

But 0b1100 = -2^3 + 2^2 = -8 + 4 = -4.

1)

What is the smallest number (in decimal) that can be represented using 7-bit two's complement binary notation?

Loading...

2)

What is the largest number (in decimal) that can be represented using 7-bit two's complement binary notation?

Loading...

An easy way to find the value of a negative two's complement number is to flip all the bits and add 1. The decimal value is then this number negated.

So to compute the value of 0b1100.

• Flip the bits: 0b0011
• Add 1: 0b0100 = 4
• Negate: Value is -4

1.1) Decimal to two's complement

3)

Write the number 19 as a 6-bit two's complement binary number:

Loading...

4)

Write the number -7 as a 6-bit two's complement binary number:

Loading...

5)

Write the number -59 as a 7-bit two's complement binary number (optional):

Loading...

1.2) Two's complement to decimal

6)

What is the decimal equivalent of the 4-bit two's complement number 0b1001?

Loading...

7)

What is the decimal equivalent of the 6-bit two's complement number 0b101101? (optional)

Loading...

8)

What is the decimal equivalent of the 5-bit two's complement number 0b01000?

Loading...

2) Floating point representation (Wikipedia)

Floating point numbers are represented using 32 bits of binary. The most significant bit represents the sign (1 is negative, 0 is positive), the next 8 bits represent the exponent +127, and the last 23 bits represent the mantissa. The mantissa encodes the fractional part of the number. The actual value of the number is sign * 2^{exponent - 127} * 1.fraction.

2.1) Floating point to decimal

To convert from floating point to decimal:

• Convert hex representation to sign_normalizedExponent_mantissa representation.
• If sign is 1, then sign is negative otherwise sign is positive.
• Find the actual exponent by subtracting 127 from the normalized exponent.
• Express numeric portion as 1.mantissa.
• If the actual exponent is positive, shift this number to the left by exponent bits. If the exponent is negative, shift this number to the right by exponent bits.
• Convert the resulting value to decimal treating each position to the left of the decimal as a positive power of 2 starting at 0, and each position to right of the decimal point as a negative power of 2.

1)

What is the decimal equivalent of the 32-bit floating point number 0x40840000?

Loading...

2.2) Decimal to Floating point

To convert from decimal floating point:

• Convert original number to base 2
• Shift number to the right or left so that the shifted number is of the form 1.mantissa. In other words, the decimal is just to the right of the leftmost 1. A shift to the left represents a negative exponent whose magnitude is the number of bits shifted, while a shift to the right represents a positive exponent. For example, 0b100.0 = 1.0 * 2^2, whereas 0.01 = 1.0 * 2^{-2}.
• Find the normalized exponent by adding 127 to the actual exponent.
• Your floating point number is sign_normalizedExponent_mantissa
• Convert the 32-bit binary representation to hexadecimal.

2)

Write the number -5.75 in 32-bit floating point representation. Write your answer in hexadecimal. 0x

Loading...

3) Pointers

Assume we have an integer x declared as

int x;

and a pointer to integer y declared as

int* y = &x;

1)

Which of the following will gain access to the address of x? (optional)

&x

*x

x++

x[]

Loading...

2)

Which of the following will gain access to the value x? (optional)

&y

*y

y++

y[]

Loading...

Track the values of each variable (a memory diagram helps).

int a = 1, b = 2, c = 3;
int *x, *y;
x = &a; // x points to a
y = &b; // y points to b
a = c; // value of a changes, so *x == a == 3
c = 0; // value of c changes, but not a, so *x == 3 still
y = x; // the address y stores becomes the address x stores, so *y == 3
*y = 5; // both x and y point to the location of a, and y just changed a, so *x == *y == a == 5

3.1) Commmon errors

What happens if you do the following?

int a = 1;
int *x;
*x = a;

This will likely segfault, since the pointer x has not been initialized to point to any particular address, so dereferencing *x goes to whatever value happened to be at the memory location of x, which could be invalid. If it doesn't segfault, then you got lucky in that the uninitialized address happened to have a valid value.

What happens if we do the following?

int *x = 0;
*x = 5

This will definitely segfault. The first line assigns an integer pointer x to hold the memory address 0x0. The next line tries to modify the value at address 0x0. That is illegal.

3.2) Using Pointers with Functions

In our simplest way to create functions, we pass in some variables and then return zero or one variable. For example, the following function takes in two inputs and returns one output.

int multiply(int x, int y) {
    return x*y;
}

Importantly in C, the inputs to functions are by default by value, meaning when we call the function, the values we pass in gets copied and used rather than the initial locations in memory. So even if we had code which utilized the multiply function from above as follows:

int hey = 5;
int hi = 17;
int bye = multiply(hey,hi);

When multiply is called, the values contained within hey and hi are copied into the scope of the function for use¹. This should make sense.

What do you do if you want to return more than one output or possibly affect more than one variable? How do you return an array? In all of these cases using pointers can be really useful. Because a pointer variable contains an address, when we pass that address into a function, we can have direct access to the memory location that stores that variable value from within the function and not just a copy of the value of the variable.

As a simple canonical example, imagine we want to swap two values, or in other words, we want a function that will take in two values and swap them, returning two values. Here's how to do that:

void main() {
  int first = 0x2F;
  int second = 0x3B;
  printf("First: %d, Second: %d", first,second);
  swap(&first, &second);
  printf("First: %d, Second: %d", first,second);
}

void swap(int* x, int* y) {
  int temp = *x;
  *x = *y;
  *y = temp;
}

Let's unpack the code. The swap function takes in two arguments, but the arguments are actually pointers. So swap is expecting some addresses to be passed in.

In app_main we declare and initialize two ints, first and second. So our memory map might look like this (again, realizing that nothing requires that first and second be adjacent to each other in memory):

But here's the trick: when we call swap in loop, we don't pass the values of first and second, we instead pass the addresses of those variables. When swap gets called it will place its local variables somewhere else in memory, and its local pointer variable x points to address 0x7530 and y points to address 0x7534. So we might have the following memory map:

In the next line, int temp = *x;, we dereference x, which holds address 0x7530, and reach out to grab the value that's being held at address 0x7530, which is 0x2F, which is then assigned to local variable temp. Another way of saying this step is temp = value pointed to by x. The memory map now looks like:

Next we dereference y to grab the value stored at the address pointed to by y. The address pointed to by y is 0x7534, and so we grab the value at that location, which is 0x3B. We then assign that value to the variable pointed at by x. Since x holds the address 0x7530, we place 0x3B into that address, which is first's address. So now first holds 0x3B. Again, this is equivalent to "value pointed at by x = value pointed at by y. The memory map now looks like:

Note that we are not changing the address held in x; to do that, we would have written something like x = y;.

Finally, we dereference y to assign the value temp to the address held in y, or "value pointed at by y = temp. Since y points to 0x7534, which is the address of second, we copy the value of temp, which is 0x2F to that memory address. The result is that we have now swapped the original values of variables first and second:

And voila, we have swapped two variables without returning anything! Study what is going on here. It is confusing at first, especially coming from a Python background, but all we're doing is exchanging the values in two memory locations.

3) Swap

Write a function that takes in two pointers to int and swaps the values that they point to.

void swap(int* a, int *b) { // your code }

Loading...

4) Square

Write a function that takes a pointer to an int as an input and returns the square of the value it points to. (optional).

(optional)

int square(int* x) { //your code return 0; }

Loading...

5) Square2

Write a function that takes a pointer to an int as an input and squares the value it points to in memory.

void square2(int* x) { //your code }

Loading...

3.3) Pointers for arrays

For reference, we list out some basic patterns in working with pointers and arrays below!

// ints
int   my_number;               // literal 8-bit signed integer
int*  my_pointer_to_a_number;  // pointer to such an int
int   my_array_of_numbers[20]; // also a pointer
// chars
char  my_character;            // literal ASCII character
char* my_pointer_to_a_char;    // pointer to such a char
char  my_array_of_chars[20];   // also a pointer
// etc.

When we define arrays, C declares spots in memory for us to use, and the resulting name (e.g. my_array) is always a pointer to the start of those spots in memory.

Dereferencing refers to taking a pointer (memory address) and working with the value at that reference. To do this, we use the asterisk *. We can use * to get the value as well as set it. And in the opposite direction, to know the memory address of some value, we use the ampersand & ("address of"). For instance,

int my_num = 5;        // define spot in memory
int* my_ptr = &my_num; // my_ptr now references my_num (which has value 5)
my_num = 20;           // change the value
*my_ptr = 300;         // change the same variable but in a spicy way

These are the fundamentals, so I suppose the minutiae comes into arrays. As mentioned, arrays are actually references in memory, AKA pointers. The [] bracket notation dereferences addresses in the same way that * does.

int8_t my_array[100];  // array of 8-bit ints
//
my_array[0] = 5;       // These three lines
*my_array = 5;         // do the same thing.
(my_array+0)[0] = 5;   //
//
my_array[3] = 15;     // And these three lines
*(my_array+3) = 15;   // do the same thing.
(my_array+3)[0] = 15; //

Understanding this makes it clear that array names are just pointers to spots in memory.

6) Array Sum

Write a function that recieves an array pointer and an array size and returns the sum of all elements in the array. Try writing this function twice. Once by accessing the array elements using a[i] and another by updating the value of the pointer and dereferencing the updated pointer to access the values of the array elements.

int array_sum(int* a, int size) { //your code return 0; }

Loading...

4) Strings in C

A null pointer is a pointer that does not point to a place in memory...well actually it does, but it points to the location "0" in memory which should not be touched. If you have a null pointer and try to dereference it, it makes our machines panic and is often responsible for crashes/exceptions being thrown.

  char ptr_1[20] = "a cat";
  printf("%s\n", ptr_1); //results in "a cat" being printed
  ptr_1[2] = 'b';
  printf("%s\n", ptr_1); //results in "a bat" being printed
  *(ptr_1+2) = 'r';
  printf("%s\n", ptr_1); //results in "a rat" being printed
  printf("%c\n", *ptr_1); //results in 'a' being printed (the character pointed to by ptr (the 0th one in the array)
  printf("%c\n", *(ptr_1+2)); //results in 'r' being printed (the character pointed to by ptr (the 2nd one in the array)
  printf("%s\n", ptr_1+2); //results in "rat" being printed the array starting at the "2"nd element of the array

  //Create a char pointer, but don't assign it to point to anything yet...it just exists now:
  char* ptr_2;
  printf("%c\n", *ptr_2); //random value...since the value ptr_2 points to is likely not a valid character/random
  //Point ptr_2 to the 2nd spot in the array pointed to by ptr_1: (currently is the 'r'):
  ptr_2 = ptr_1+2;
  printf("%c\n", *ptr_2); //results in 'r' being printed
  printf("%s\n", ptr_2); //results in "rat" being printed since it is pointing to the second value of the array pointed to by ptr_1

  char x = 'x';
  //now change where ptr_2 is pointing by assigning it the ADDRESS (&) of x
  ptr_2 = &x;
  printf("%c\n", x); //results in 'x' being printed
  printf("%c\n", *ptr_2); //results in 'x' being printed
  printf("%ld\n", (int) ptr_2); //results in large number (corresponding to x's memory address) being printed)
  printf("%ld\n", (int) &x); //results in large number (corresponding to x's memory address) being printed)

  //change the value contained in the memory spot contained by ptr_2:
  *ptr_2 = 'y';
  printf("%c\n", *ptr_2);//prints 'y';
  printf("%c\n", x); //prints 'y'...since its value was changed through ptr_2
  printf("%s\n", ptr_2); //could potentially cause a crash since printing a char* means it is treated as a string and expects a null terminator somewhere...if there is no null (aka int 0) reasonably close in the stack this will cause a crash
  //...so this crash is possible, but not guaranteed, for a lone character

1) String index

Write a function that recieves a string and a character as inputs and it returns the first index at which that character is found in the string or -1 if its not found. Again, write this using array indeces and then rewrite it by updating the pointers and dereferencing them to access the string's characters.

int string_index(char *s, char c) { //your code return 0; }

Loading...

5) Pointers to pointers

int x = 60004, y = 314;
int *ptr, *ptr2;
ptr = &x; // ptr points to x, so *ptr == 60004
int **ptr_to_ptr;
ptr_to_ptr = &ptr; // ptr_to_ptr points to ptr, so *ptr_to_ptr == ptr and **ptr_to_ptr == 60004
x = 0; // we still have **ptr_to_ptr == *ptr == x, just now they're all 0
*ptr = 1; // we still have **ptr_to_ptr == *ptr == x, just now they're all 1
ptr2 = &y;
*ptr_to_ptr = ptr2; // This is tricky! Draw a diagram with what everything points to and what value everything has.
// Answer: We still have *ptr_to_ptr == ptr1. Since we assigned the new value to ptr2, now ptr1 == ptr2. In particular this means **ptr_to_ptr == *ptr == *ptr2 == y == 314
y = 77; // Changing the value of y changes all of the above equalities!
// But what is x? Nothing points to x anymore, so we still have x == 1
x = 2; // This changes x, but none of our pointers are related to x anymore so nothing else changes