Volume Number: 23 (2007)
Issue Number: 09
Column Tag: The Road to Code

The Road to Code: Bits and Bytes and Everything Nice

More Memory Topics

by Dave Dribin

Last month in The Road to Code, we went over control statements, such as loops and conditional statements, as well as pointers. This month, we will be going over arrays and dynamic memory. Dynamic memory is used heavily in Objective-C, but I think the concepts are better demonstrated with straight C.

A topic that goes hand in hand with pointers is arrays. Arrays are a collection of items of the same type. For example, let's say we want to keep track of the first three even numbers. We could use three separate variables, but that's a little tedious. Fortunately, there's another option. We can use an array, which is a single variable that holds multiple values. For example, see Listing 1.

Listing 1: main.c Simple arrays

#include <stdio.h>
int main(int argc, const char * argv[])
{
   int evens[3];
   evens[0] = 2;
   evens[1] = 4;
   evens[2] = 6;
   
   printf("evens[0] = %d\n", evens[0]);
   printf("evens[1] = %d\n", evens[1]);
   printf("evens[2] = %d\n", evens[2]);
    return 0;
}

evens[0] = 2
evens[1] = 4
evens[2] = 6

Digging into this example, the first odd thing you'll notice is the declaration of the evens variable. It starts off like other variable declarations with a type and a name, but after the name you'll see the square brackets with the number three in it: [3]. The square brackets tell the compiler that we are declaring an array of integers, instead of a single integer, and the number inside the brackets is how many items the array may hold. So, in this case, evens is an array that may hold three integers.

The second odd thing is how we are getting and setting the values of the array. Again, we use the square brackets to tell the compiler which item in the array we want to access. The number between the brackets is called an array index. This brings us to the first important bit of information: the first item in the array has an index of 0. Thus, the second item has an index of 1, and the last item has an index of 2. Even though this array has three items, the index ranges from 0 to 2. In fact, the last index of any array is the number of items minus one. It is important to remember this because the C compiler will not remind you. It will happily allow you to accesses index 3 of a three-item array. This kind of bug is very serious, and causes all sorts of trouble. So always be sure to double-check your array indexes!

The nice thing about arrays is that you can make them bigger to hold more items very easily. If we wanted to hold the first five even numbers, we just need to make our array bigger. In order to reduce code repetition, we can use for loops to initialize and print out the array:

Listing 2 main.c Using for loops with an array

#include <stdio.h>
int main(int argc, const char * argv[])
{
   int evens[5];
   int i;
   for (i = 0; i < 5; i++)
      evens[i] = (i+1) * 2;
   
   for (i = 0; i < 5; i++)
      printf("evens[%d] = %d\n", i, evens[i]);
    return 0;
}

This example shows that array indexes may be a variable, instead of a constant number. We are using the variable i to loop over all the indexes of the array. Note the condition of the for loop: i < 5. Using a less than operator ensures i loops from 0 to 4. This code is now more extensible because of the array and for loops. We can easily create an array to hold the first 100 even numbers. But we still have to change the number five in three different places. You may be wondering if we can eliminate this repetition as well, and it turns out that we can.

Preprocessor Macros

In order to reduce this kind of code repetition, the C language has what is called a preprocessor. The preprocessor allows you define macros that perform a search and replace on your code. Let's see how this can help us:

Listing 3: main.c Using a preprocessor macro

#include <stdio.h>
#define ARRAY_SIZE 5
int main(int argc, const char * argv[])
{
   int evens[ARRAY_SIZE];
   int i;
   for (i = 0; i < ARRAY_SIZE; i++)
      evens[i] = (i+1) * 2;
   
   for (i = 0; i < ARRAY_SIZE; i++)
      printf("evens[%d] = %d\n", i, evens[i]);
    return 0;
}

The second line in this program defines a new macro named ARRAY_SIZE. This tells the compiler to replace all uses of ARRAY_SIZE with the number five. The command to define a new macro is #define. Because the first character of this command is the pound character, this kind of macro definition is often called a pound define. While a pound define is very similar to setting a variable, you should not use an equal sign or a semicolon. If we used:

#define ARRAY_SIZE = 5;

Then, the evens declaration would result in invalid C syntax, after the macro replacement:

   int evens[= 5;];

With our new macro in place, changing the array size to ten can be accomplished with one simple change:

#define ARRAY_SIZE 10

Arrays as Pointers

So what's this about arrays and pointers being similar? As it turns out, pointers and arrays can often be used interchangeably in C. A pointer to an integer, int *, can be set to an array without any conversion necessary:

Listing 4: main.c Using pointers and arrays

#include <stdio.h>
#define ARRAY_SIZE 5
int main(int argc, const char * argv[])
{
   int evens[ARRAY_SIZE];
   int * pointer;
   int i;
   for (i = 0; i < ARRAY_SIZE; i++)
      evens[i] = (i+1) * 2;
   
   pointer = evens;
   for (i = 0; i < ARRAY_SIZE; i++)
      printf("pointer[%d] = %d\n", i, pointer[i]);
    return 0;
}

We set the variable pointer to be equal to the array evens without using an ampersand, &, the address of operator, like we did in last month's article. Also, notice that the compiler lets us use an array index on the pointer variable, just like an array. This is because pointers and arrays are virtually the same in C. You do have to be very careful when using pointers as arrays, though. The C compiler does not know that pointer points to an array, instead of an ordinary variable. The compiler simply assumes that if you are trying to access a pointer as an array, you must be right. You can easily introduce subtle and hard to find bugs, so be careful.

If it's so dangerous, why should we use it? In these examples, the sizes of the arrays are set in stone when we compile them. If we want to change the size of the array when the program is running, we have to use pointers as arrays. But before we go over how to do this, we need to take a step back and look under the hood a bit. We need to further understand how computer memory works.

Over the last couple of articles, I've been using a box analogy for variables. Each variable is like a box that holds a specific type of data, such as an integer or floating point number. Also, each box is assigned a unique address, which I compared to a P.O. Box number. But real boxes typically hold physical objects like shoes or books. What is a number, and how can a box hold one? Do numbers have certain physical characteristics? It turns out they do, and it all revolves around ones and zeroes.

Internally, computers only understand two digits: 0 and 1. Everything a computer does, from the simple math, to complex graphics and sound all boil down to 0 and 1. So how can computers count higher than 1? It's very similar to normal decimal numbers, where we only have ten digits, 0 through 9. By stringing together multiple digits, we can count much higher than 9, to numbers such as 523. Computers can string together multiple zeros and ones, too, to make larger numbers, such as 1101. Because computers only deal with two digits, instead of the usual ten, these numbers are called binary numbers. Since humans better understand decimal numbers, we need to be able to convert binary numbers, such as 1101, back into normal decimal numbers and vice versa.

To convert binary numbers, we once again have to drudge up some simple math. Normal decimal numbers we use every day are called base-10 numbers because there are 10 digits, 0 through 9. When digits are strung to create a larger number, like 523, each digit carries a certain weight. The base-10 number 523 can be expressed as a simple equation:

52310 = 5x100 + 2x10 + 3x1 = 500 + 20 + 3

The numbers 1, 10, and 100 are the weight of each digit. As we add more digits, the weight goes up by another power of 10 to 1,000, then 10,000, and so on. The small 10 subscript is the mathematical way of clarifying we are talking about a base-10 number. We don't normally include this subscript, as we nearly always deal with base-10 numbers.

Binary numbers work similarly, except there are only two digits available, 0 and 1. To convert a binary number to decimal, we can use base-10 numbers as the weight of each digit. Instead of each weight going up by a power of 10, they go up by a power of 2, i.e. 1, 2, 4, 8, 16, etc. Because binary numbers are based around powers of 2, they are called base-2 numbers and a small 2 subscript may be used to denote a binary number. Thus the 11012 binary number can be converted to 1310 using the power of 2 weights:

11012 = 1x8 + 1x4 + 0x2 + 1x1 = 8 + 4 + 1 = 1310

Because the use of 0 and 1 for the digits of binary numbers, they have been given the shorthand name of bit, which is a contraction of binary digit. Binary numbers are often classified by how many bits they have, thus 11012 is considered a 4-bit number.

Bytes

As we combine more bits together into one binary number, we can start representing larger and larger numbers. When we have a binary number with eight bits, we can represent a number between 0 and 255. This is because the largest 8-bit binary number is 111111112. If we expand this out, using the weight of each digit, we get:

111111112 = 1x128 + 1x64 + 1x32 + 1x16 + 1x8 + 1x4 + 1x2 + 1x1 = 25510

For historic reasons, these 8-bit numbers are the basis of all modern computing and are given a very special name of their own: a byte. Thus a single byte can represent any decimal number from 0 to 255.

Even though we usually let the compiler translate decimal numbers to binary, sometimes you have to deal directly with bits. Unfortunately, binary numbers can be very tedious for people to write out. To make it easier to represent long binary numbers, without converting to decimal, the computer scientists invented a new notation called hexadecimal numbers or just hex for short. Hexadecimal numbers are base-16 numbers that have 16 digits with the weight of each digit being a power of 16. The only problem is that there are not 16 digits available: only 10. Those clever computer scientists decided to borrow the first 6 letters of our alphabet, A through F, to fill in the blanks. Because all of these number conversions can get quite confusing, I've created Table 1 to help convert between binary, hexadecimal, and decimal numbers.

Table 1: Binary, Hexadecimal, Decimal Conversion Chart

Binary Number   Hexadecimal Number   Decimal Number   
              0000                 0                      0   
              0001                 1                      1   
              0010                 2                      2   
              0011                 3                      3   
              0100                 4                      4   
              0101                 5                      5   
              0110                 6                      6   
              0111                 7                      7   
              1000                 8                      8   
              1001                 9                      9   
              1010                 A                      10   
              1011                 B                      11   
              1100                 C                      12   
              1101                 D                      13   
              1110                 E                      14   
              1111                 F                      15   

To convert larger hexadecimal numbers to decimal, we have to resort to power of 16 digit weights. For example, to convert the hexadecimal number 5FC16 to decimal, we first convert each hexadecimal digit to decimal using Table 1, and then use powers of 16 as the digit weights:

5FC16 = 5x256 + 15x16 + 12x1 = 1280 + 240 + 12 = 152310

Using Table 1, we can convert any 4-bit binary number easily to hexadecimal. Converting larger binary numbers to hexadecimal numbers does not even require any math. We just group together 4 bits, and use Table 1 on each group. For example to convert 110110012 to hexadecimal, we first chop it up into 2 groups: 11012 and 10012. Then, converting each group of four, we get D916. If we wanted to convert this number to decimal, we can use the power of 16 weights, again:

110110012 = D916 = 13x16 + 9x1 = 208 + 9 = 21710

This grouping of 4-bits is called a nibble, sometimes spelled nybble. By breaking large binary numbers up into nibbles, it's easy convert them into hexadecimal no matter how many bits you have. With words like bits, bytes, and nibbles, it's easy to see why computer scientists have such a good sense of humor.

How do bits and bytes relate to programming variables? All of the boxes used for the variables in your program are stored in the computer's memory. Your computer's memory, called RAM (short for Random Access Memory) is like the post office, where all P.O. Boxes live. Each box is given a unique number, an address, and each one has the same size. The fundamental size of each box is one byte. But wait... I said earlier that one byte could only hold a number from 0 to 255. So how can an integer variable in C store larger numbers? Well, the C compiler uses multiple, consecutive bytes to create a bigger box. Typically, it uses four bytes, or 32 bits for a variable of type int, which is big enough to hold numbers from 0 to 4,294,967,295. That's just over four billion.

What about negative numbers? Computers steal one bit and use it as the sign of a number. This conversion of negative numbers to binary is called two's complement. I don't have enough space to fully cover two's complement in this article. If you want to learn more, Wikipedia has a good article [1] that is a great place to start. The end result of using two's complement means that int, a signed 32-bit integer, can only hold numbers between -2,147,483,648 and 2,147,483,647. If you need to use larger numbers, and you do not need to use negative numbers, you can use the unsigned int data type when you declare your variables to tell the compiler not to use 1 bit for the sign.

The C compiler has a special operator, called sizeof, that returns the number of bytes a variable or data type uses. This operator works like a function, and you pass a variable or type as the argument. For example, this line of code will print 4:

   printf("%d\n", sizeof(int));

Because all programs have different needs, the C language has other integer data types that are stored using a different number of bytes.

Table 2 (above) summarizes the standard integer data types and the number of bytes they use on a 32-bit Mac OS X program. By default, these data types are signed. You can use the unsigned keyword in front of any of these types if you only care about positive numbers.

I specifically said "a 32-bit Mac OS X program," because the C language does not make any guarantee of these sizes on other operating systems and processors. For example, on a 64-bit Intel Mac OS X program, sizeof(long) is not four bytes, it's eight. If you really, really care about the number of bytes a variable uses, you should use one of the newer data types. In 1999, signed integer data types of the format intxxx_t, where xxx is a number of bits: 8, 16, 32, or 64 were added. So if you really want a 32-bit signed integer, you would use int32_t. There are also unsigned variants, which use uintxxx_t. So an unsigned 8-bit integer type would be uint8_t. These new types are available in the stdlib.h header file. Listing 6 demonstrates the sizeof operator and these new data types.

Listing 5: main.c demonstrating sizeof

#include <stdio.h>
#include <stdlib.h>
int main(int argc, const char * argv[])
{
   long foo;
   unsigned long bar;
   
   printf("sizeof(foo) = %d\n", sizeof(foo));
   printf("sizeof(bar) = %d\n", sizeof(bar));
   printf("sizeof(uint8_t) = %d\n", sizeof(uint8_t));
   printf("sizeof(uint16_t) = %d\n", sizeof(uint16_t));
   printf("sizeof(uint32_t) = %d\n", sizeof(uint32_t));
   printf("sizeof(uint64_t) = %d\n", sizeof(uint64_t));
   
   return 0;
}

Sizes of Computer Addresses

Most computer processors from the 1980s and 1990s use 32-bit numbers internally for addresses, too. Computer processors are classified by the number of bits used for addresses, thus these processors are classified as 32-bit processors. This means a 32-bit processor only has enough addresses for slightly over four billion bytes of memory, at it's maximum. Since 1 billion bytes, or more precisely 1,073,741,824 bytes, is called a gigabyte, a 32-bit processor is said to address a maximum of four gigabytes. While this may seem like a lot, this may not be enough for some applications.

You may have heard some buzz about "64-bit." In fact, 64-bit Cocoa support is one of the new major features of Leopard. Newer computer processors, like the PowerPC G5 and the Intel Core 2 Duo, can use 64-bit addresses. This allows the computer to access more than four gigabytes of memory, which speeds up some programs that work on large amounts of data, such images, videos, and scientific data.

When you declare a variable inside a function, the compiler automatically sets aside the number of bytes necessary for its storage. This setting aside of memory is called allocating memory. Once the function finishes executing, the allocated memory is automatically given back to the system, called deallocating memory. When the compiler handles memory allocation for you, this is called automatic memory allocation. Because the memory of variables inside a function are allocated and deallocated automatically, they are sometimes referred to as automatic variables.

Sometimes this automatic memory allocation is not good enough, and you have to take matters into your own hands. The standard C library has a function named malloc that allocates the specified number of bytes of memory and returns the address of this new memory. You can assign this address to a pointer, and then use it like we used pointers in last month's article. Because you manually allocated the memory, you must also deallocate it yourself using the free function. When you take control of memory allocation, this is called dynamic memory allocation, or dynamic memory, for short. Listing 8 is a simple example of dynamic memory.

Listing 6: main.c Using dynamic memory

#include <stdio.h>
#include <stdlib.h>
int main(int argc, const char * argv[])
{
   int * pointer;
   pointer = malloc(sizeof(int));
   *pointer = 5;
   printf("*pointer = %d\n", *pointer);
   free(pointer);
   
   return 0;
}

Along with great power comes great responsibility. As such, it's very important to deallocate memory that you allocate. Failing to return memory to the system is called a memory leak. Memory leaks are a serious class of bugs that can affect the performance of your program and the entire system. There are no magic ways to avoid memory leaks in C. You just have to be very careful and make sure you free any memory you allocate with malloc. Memory that is leaked by your application is reclaimed when your application exits. This doesn't mean leaks should be ignored, however. Leaked memory limits the amount of memory available for other tasks, and can slow down the entire system. Objective-C has some techniques to avoid memory leaks, which we will cover in due time.

Dynamic Memory for Arrays

Using dynamic memory, as previously shown in Listing 8, provides no benefit to automatic memory. One real reason to use dynamic memory is when we want to change the size of an array while the program is running. To demonstrate this, let's look at Listing 10, which reads numbers from the user, and prints them in reverse order:

Listing 7: main.c Printing numbers in reverse

#include <stdio.h>
#define MAX_LENGTH 25
void read_numbers(int array[], int length)
{
   int i;
   for (i = 0; i < length; i++)
   {
      printf("Enter number %d: ", i+1);
      scanf("%d", &array[i]);
   }
}
void print_in_reverse(int array[], int length)
 {
   int i;
   for (i = length-1; i >= 0; i--)
   {
      printf("%d\n", array[i]);
   }
}
int main(int argc, const char * argv[])
{
   int numbers[MAX_LENGTH];
   int length;
   
   printf("How many numbers? ");
   scanf("%d", &length);
   if (length < 1)
   {
      printf("Choose a number greater than or equal to 1\n");
      return 1;
   }
   
   if (length > MAX_LENGTH)
   {
      printf("Choose a number less than or equal to %d\n",
            MAX_LENGTH);
      return 1;
   }
   
   read_numbers(numbers, length);
   print_in_reverse(numbers, length);
   return 0;
}

In this program, we have an array of integers, numbers, that has a size of MAX_LENGTH, which is set to twenty-five. The first thing it does is ask the user how many numbers they are going to type in. It does some error checking on this number to make sure it's not too big or too small. Then, it reads that many numbers into the array. Finally, it prints them out in reverse order. I also introduce some new syntax. When arrays are used as arguments to functions, they cannot include a size. Thus, you use square brackets without a number, for example array[].

Here is a sample run of this program:/P>

How many numbers? 4
Enter number 1: 42
Enter number 2: -3
Enter number 3: 523
Enter number 4: 11
11
523
-3
42

Great, it seems to work as designed! Unfortunately, this program has one limitation: the user can only enter twenty-five numbers. What if the user wanted to enter 100, or even 1,000 or 1,000,000 numbers? Sure, we could change MAX_LENGTH, but this is always going to be a guessing game. And if we make MAX_LENGTH very large, then we are wasting memory when the user only wants to enter a few numbers. The solution is to use dynamic memory.

Listing 8: main.c Dynamic size of an array

#include <stdio.h>
#include <stdlib.h>
void read_numbers(int array[], int length)
{
   int i;
   for (i = 0; i < length; i++)
   {
      printf("Enter number %d: ", i+1);
      scanf("%d", &array[i]);
   }
}
void print_in_reverse(int array[], int length)
{
   int i;
   for (i = length-1; i >= 0; i--)
   {
      printf("%d\n", array[i]);
   }
}
int main(int argc, const char * argv[])
{
   int * numbers;
   int length;
   
   printf("How many numbers? ");
   scanf("%d", &length);
   if (length < 1)
   {
      printf("Choose a number greater than or equal to 1\n");
      return 1;
   }
   
   numbers = malloc(length * sizeof(int));
   read_numbers(numbers, length);
   print_in_reverse(numbers, length);
   free(numbers);
   
   return 0;
}

In Listing 8, we changed the type of numbers from an array to a pointer. After getting length from the user, we allocate the needed memory with malloc. Because numbers is now a pointer – and pointers are interchangeable with arrays – we don't have to change the arrays in the function arguments.

The trick for using malloc on arrays is to use the sizeof operator to allocate the correct number of bytes. Remember that each integer uses four bytes of memory. Thus, five integers require twenty bytes of memory. This is why we multiply length by sizeof(int). By using malloc to allocate memory, we've solved two issues. First, the only limit on the size of the array is the amount of memory the user's computer has. We can eliminate the MAX_LENGTH constant and our error checking on the maximum size. Second, we are only allocating memory that we need. We are not wasting memory by only using a portion of a larger array.

This also demonstrates the importance of using the sizeof operator, instead of hard coding the number four. You don't have to remember how many bytes an integer uses. It also makes your program more portable. Because an integer may use a different number of bytes on a different computer, this program will compile on any platform that can compile C. While you may not plan on running your software on a different computer, it's impossible to see the future. Even if you stick to writing only Mac software, Apple has switched processors a number of times, from 68000, to PowerPC, and now Intel. Who knows what Macs will be running on in another ten years?

We've covered a lot of background information in this article. While these examples may seem trivial, the basic concepts they illustrate lie at the heart of Objective-C and programming for Mac OS X. Once we finally get to some "real" Mac programming, our time spent going over all this background information will be time well spent.

[1]: Wikipedia Two's Complement article. http://en.wikipedia.org/wiki/Twos_complement

Dave Dribin has been writing professional software for over eleven years. After five years programming embedded C in the telecom industry and a brief stint riding the Internet bubble, he decided to venture out on his own. Since 2001, he has been providing independent consulting services, and in 2006, he founded Bit Maki, Inc. Find out more at http://www.bitmaki.com/ and http://www.dribin.org/dave/.