CS 208 f21 — Integer Representation

• how many bytes does it take to represent the string "strangelove" in C?¹
• how would you define a struct to represent a 2D point?²

Though memory is a long array of bytes, it is actually separated into various segments or memory regions. Memory allocated at compile time is located on the stack, which resides at high addresses in memory. As more data is added to the stack, the region grows to include lower addresses, so we say the stack grows down.

Memory allocated dynamically using malloc is placed on the heap, which resides somewhere in the middle of memory. As more data is added to the heap, the region grows to include higher addresses, so we say the heap grows up.

The other three regions (static data, literals, and instructions) are fixed in size and get initialized when a program starts running.

• We can dynamically allocate storage space while the program is running, but we cannot create new variable names "on the fly"
• For this reason, dynamic allocation requires two steps:
  1. Creating the dynamic space.
  2. Storing its address in a pointer (so that the space can be accesed)
• To dynamically allocate memory in C, we use the malloc function provided by stdlib.h
  • malloc takes in a number of bytes to allocate and returns a pointer to the newly allocated space
  • malloc does not do any initialization, so the contents of this memory can be whatever was last written to those bytes
    • this means you must always perform initialization on memory return by malloc
• De-allocation:
  • Deallocation is the "clean-up" of space being used for variables or other data storage
  • Compile time variables are automatically deallocated based on their known extent
  • It is the programmer's job to deallocate dynamically created space
  • To de-allocate dynamic memory, we use the free function operator
    • free takes a pointer that was previously returned by malloc and makes that memory available for future allocation
    • free has undefined behavior is used with a pointer that wasn't returned by malloc or a pointer that was already freed

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 notes³.

#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);
}

Recall the example from the first topic where 200 * 300 * 400 * 500 resulted in -884901888? Over the next two topics studying how integers are represented on computer systems, we will see why exactly this happens.

To start with the simpler case, let's look at unsigned integers. Though no type in C uses only 4 bits, I'll be using 4-bit representations to introduce integer concepts. Fewer bits will make it easier to see what's going on and do quick practice problems.

For unsigned integers, we will count each bit as its positive weight. Below are all 16 4-bit unsigned integers in decimal and binary:

Think about what should happen if we add 1 to 0b1111. Remember we only have 4 bits to work with. You'll see what computers actually do in Wednesday's topic.

Consider the two following possibilities for a 4-bit signed integer representation:

• sign and magnitude: the most significant bit indicates positive (0) or negative (1), the other bits count as their weight
  • 0b0011 would be 3, 0b1011 would be -3
• two's complement: the most significant bit counts as its negative weight (-8), the other bits count as their positive weight
  • 0b0011 would be 3, 0b1101 would be -3 (\(-8 + 4 + 1 = -3\))
  • why "two's complement"? Comes from the fact that \(-n\) is represented as the difference of a power of 2 and \(n\), specifically \(2^w - n\)
    • Can see this in 0b1101 for -3: \(w = 4\) (4-bit-wide representation), \(2^4 - 3 = 16 - 3 = 13 =\) 0b1101

• 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

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 integers⁴:

   • 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

Kilobyte (KB), megabyte (MB), and gigabyte (GB) refer to 2¹⁰, 2²⁰, and 2³⁰ bytes respectively. They are also used to refer to 10³, 10⁶, and 10⁹ bytes in some contexts.