CS 208 s21 — Learning Block #4

Table of Contents

1 Review

Practice your what you've been learning about C by finding the the problems with the code below. I've noted the lines where compiler errors occur—try and figure out how you would resolve them. Once those are fixed, there are two potential run-time errors. These may crash the program, or not affect it at all (ah, the fun of working closely with memory in C). See if you can spot them, and then check your thinking at the end of these notes1. 

#include <stdlib.h>
#include <string.h>

typedef struct node {
    struct node *left;
    struct node *right;
    char *value;
} node_t;

int main() {
    char *s = "noodles";
    node_t *root = (node_t*) malloc(node_t);  // gcc error: expected expression before ‘node_t’
    if (*root == NULL) {  // gcc error: invalid operands to binary == (have ‘node_t {aka struct node}’ and ‘void *’)
        return 1;
    }
    *root->left = NULL;  // gcc error: incompatible types when assigning to type ‘struct node’ from type ‘void *’
    *root->right = NULL;  // gcc error: incompatible types when assigning to type ‘struct node’ from type ‘void *’
    root->value = (char*) malloc(sizeof(char));
    strcpy(root->value, s);
    free(root);
    free(root->value);
}

2 QUICK CHECK

  • Take the 4‐bit number encoding where x = 0b1011
  • Which of the following numbers is NOT a valid interpretation of x using any of the number representation schemes discussed in the video for today? (Unsigned, Sign and Magnitude, Two’s Complement)
    a. -4
    b. -5
    c. 11
    d. -3

3 Practice

  1. CSPP practice problems 2.17 (p. 65) and 2.19 (p. 71)
    • for 2.17, \(B2U_4\) means interpret the bits as 4-bit unsigned, \(B2T_4\) means interpret the bits as 4-bit two's complement
    • for 2.19, \(T2U_4\) means convert from 4-bit two's complement to 4-bit unsigned
  2. Considering 8-bit integers2:
    • What is the largest integer?
      Unsigned: Two's Complement:
         
    • How do you represent (if possible) the following numbers: 39, -39, 127?
      Unsigned Two's Complement
      39: 39:
      -39: -39:
      127: 127:

It will be useful to have the powers of 2 at your fingertips as we go through this course, so here's a table of those

\(n\) \(2^n\) \(n\) \(2^n\)
1 2 16 65536
2 4 17 131072
3 8 18 262144
4 16 19 524288
5 32 20 1048576
6 64 21 2097152
7 128 22 4194304
8 256 23 8388608
9 512 24 16777216
10 1024 25 33554432
11 2048 26 67108864
12 4096 27 134217728
13 8192 28 268435456
14 16384 29 536870912
15 32768 30 1073741824

Kilobyte (KB), megabyte (MB), and gigabyte (GB) refer to 210, 220, and 230 bytes respectively. They are also used to refer to 103, 106, and 109 bytes in some contexts.

Footnotes:

1 
#include <stdlib.h>
#include <string.h>

typedef struct node {
    struct node *left;
    struct node *right;
    char *value;
} node_t;

int main() {
    char *s = "noodles";
    node_t *root = (node_t*) malloc(sizeof(node_t));  // use sizeof with the type to get the number of bytes 
    if (root == NULL) {  // compare the pointer to NULL (we want to check if malloc failed---it returns NULL in that case)
        return 1;
    }
    root->left = NULL;  // we want to assign the pointer left itself to NULL 
                        // rather than writing NULL to the address it points to (what the * was doing)
    root->right = NULL;  // we want to assign the pointer right itself to NULL
    root->value = (char*) malloc(sizeof(char));  // RUNTIME ERROR this allocates space for 1 char, 
                                                 // use malloc(strlen(s) + 1)  * sizeof(char)) instead
    strcpy(root->value, s);
    free(root);
    free(root->value);  // RUNTIME ERROR we are accessing root after freeing it, 
                        // this has undefined behavior (free root->value first, then free root)
}
2

Considering 8-bit integers:

  • What is the largest integer?
    Unsigned: Two's Complement:
    255 127
  • How do you represent (if possible) the following numbers: 39, -39, 127?
    Unsigned Two's Complement
    39: 0b00100111 39: 0b00100111
    -39: not possible -39: 0b11011001
    127: 0b01111111 127: 0b01111111