Part 7½ Advanced programming

Incrementing and decrementing shorthands

So far, I've been very careful to use code like i =i +1 to increment a variable. But C provides a handy shorthand for incrementing and decrementing values. Using ++ with a variable will add one to a value, and −− will subtract one from a value. Many programmers use this shorthand in their code, so you should know how to use it.

There's a fine point in how to use this shorthand. Both i++ and ++i will add one to the variable i, but will do so in a different order. When you use ++ before the variable, C will add one to it before referencing the value in a statement. If you use ++ after the variable, C will use the variable's current value and then will add one to it.

This is an important point. If you aren't careful, using the operator in the wrong order can result in obscure and interesting bugs.

Let's take a look at how to use these operators in a program, and what they do. This sample program just demonstrates using ++ and −− in different orders:

#include <stdio.h>

int
main()
{
   int a = 0;
   int b = 0;

   /* print a and b */

   printf("a is %d\n", a);
   printf("b is %d\n", b);

   /* demonstrate ++ */

   printf("the value of 'a++' is %d\n", a++);
   printf("the value of '++b' is %d\n", ++b);

   /* print a and b */

   printf("a is %d\n", a);
   printf("b is %d\n", b);

   /* demonstrate -- */

   printf("the value of 'a--' is %d\n", a--);
   printf("the value of '--b' is %d\n", --b);

   /* print a and b */

   printf("a is %d\n", a);
   printf("b is %d\n", b);

   return 0;
}

The result will be:

a is 0
b is 0
the value of 'a++' is 0
the value of '++b' is 1
a is 1
b is 1
the value of 'a--' is 1
the value of '--b' is 0
a is 0
b is 0

Another handy shorthand is a modification to the equals operator. For example, when you need to do things like i=i+1; you can use a shorthand like this: i += 1;. This shorthand effectively says “take what's on the left and add what's on the right.”

C has several shorthands around the equals, including:

Be careful when using these shorthands, however. They can be useful when used carefully, but they can also introduce very interesting bugs. Here's one example:

x *= y + 1;

This is the equivalent of x = x * (y + 1) and not x = x * y + 1. What's on the right is taken as a unit when using this shorthand.

In that example, if x already had the value of 2 and y had the value of 1, then:

x *= y + 1;

…should correctly calculate the value of 2×(1+1) which gives 2×2 or x=4.

If you expected the calculation the other way, you would have the wrong result of 2×1+1 which is 2+1 or x=3.

Binary values and operators

C is a very low-level programming language. While not quite at the "hardware" level as Assembly, C is still pretty "close to the ground." As such, it sometimes helps to think like a computer when you're programming in C.

Let's take a moment to consider how computers actually store values. The computer doesn't store the values 1,2,3,… as literal numbers. Instead, the computer stores these as a series of zeroes and ones, called bits, in a format called binary. Because it only deals with zero and one, binary numbers look quite different from the base-ten numbers that we usually work with.

Think about how you count in base-ten. Counting from zero, you have numbers like:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, …

In base-ten numbers, the "ones" place is on the right. To the left of that is the "tens" place. Then hundresds, thousands, and so on. Each "place" represents a power of ten, because this is "base-ten." For example, 2 in the tens place and a 1 in the ones place means twenty-one.

Binary numbers count using zeroes and ones, but the ordering is basically the same. In binary, the "ones" place is on the right. To the left of that is the "twos" place. Then "fours," "eights," and so on. Each "place" represents a power of two, because binary is "base-two."

Numbers in binary are then just a collection of bits, each zero or one. An 8-bit system would track binary numbers eight bits at a time:

Eight bits that are all ones would be 128+64+32+16+8+4+2+1=255. That means eight bits can count from 0 to 255, or a range of 256 (2⁸) values. And sixteen bits can track up to 65536 (2¹⁶) values.

That means a binary number like 0011 is the base-ten value of 3 because you have a 1 in the "ones" place and a 1 in the "twos" place. (Add "one" and "two" together and you get three.) Similarly, the binary number 0110 is 6 in base-ten because you have a 1 in the "twos" place and a 1 in the "fours" place. (Add "two" and "four" together and you get six.)

Binary makes things much easier on the computer. Computers can store a binary 1 (usually a "high" voltage value in some part of the electronics) or a binary 0 (such as a "low" voltage value) very easily. Counting in binary is as easy for a computer as counting in base-ten is to you and me.

And that's why it sometimes helps to think like a computer when you're programming in C. Especially when you are working with binary values. When you store a value like 3 in an integer variable, C actually stores the binary value 0011.

Knowing the binary representation for different values is very useful in certain situations. And so is knowing how to operate on these binary values.

C provides several binary operators you can use in your programs:

When you use a bitwise AND on two values, such as 1&3, the computer will compare each bit in both numbers. When each position is a 1, AND results in a 1. Otherwise, AND results in a 0. So 1&3 is 1. This is easier if we write each number in binary, and display them so they line up on different lines:

  0001
& 0011
= 0001

The bitwise OR combines the bits in each value. When either position is a 1, OR results in a 1. If neither is 1, OR results in 0. That means 1|3 results in 3.

  0001
| 0011
= 0011

The bitwise XOR (exclusive OR) compares the bits in a different way. XOR outputs 1 only when the bits differ. If the bits are the same, XOR gives 0. So 1^3 is 2.

  0001
^ 0011
= 0010

The bitwise NOT is a simple binary operator. For each position that contained 1, you get 0. And for each position that contained 0, you get 1. This essentially "flips" the bits between 1 and 0.

 ~0001
= 1110

This demonstration program shows how to use the different binary operators:

#include <stdio.h>

int
main()
{
   int a = 1;
   int b = 2;

   /* the binary of 1 is 0001 */
   /* the binary of 2 is 0010 */

   printf("'a' is %d\n", a);
   printf("'b' is %d\n", b);

   puts("binary goes like 8 4 2 1");

   puts("the binary of 1 is 0001");
   puts("the binary of 2 is 0010");

   /* binary AND, inclusive OR, exclusive OR (XOR) */

   /* 0001 & 0010 is 0000 because none of the 1's line up */
   /* 0001 | 0010 is 0011 because you basically combine the 1's */

   printf("'a & b' is %d\n", a & b);
   printf("'a | b' is %d\n", a | b);

   /* 0011 ^ 0010 is 0001 because XOR sets 1 where the bits are different and 0 where they are the same */

   puts("XOR sets 1 where the bits are different");
   puts(" ... and 0 where the bits are the same");

   puts("the binary of 3 is 0011");
   puts("the binary of 2 is 0010");

   printf("'3 ^ 2' is %d\n", 3 ^ 2);

   /* one's complement */

   puts("~1 flips 1s and 0s");

   printf("'~1' as %%d is %d\n", ~1);
   printf("'~1' as %%u is %u\n", ~1);

   return 0;
}

The bitwise shifts are a powerful way to move bits around. Literally, the bitwise shift will shift the bits left or right by a certain number of bits. Remember that base-ten 6 is binary 0110. Shifting these bits to the left by one place will give 1100, or the base-ten value of 12. Shifting 1100 to the right by two places will give 0011, or base-ten 3.

  0110<<1
= 1100

  1100>>2
= 0011

This sample program shows this bit shift manipulation:

#include <stdio.h>

int
main()
{
   int a = 1;

   printf("'a' is %d\n", a);
   puts("the binary of 1 is 0001");

   /* binary shift */

   puts("binary 0010 is 2");
   printf("'a << 1' is %d\n", a << 1);

   puts("binary 0100 is 4");
   printf("'a << 2' is %d\n", a << 2);

   /* shift different values */

   puts("binary goes like 8 4 2 1");

   for (a = 0; a <= 3; a++) {
      printf("'1 << %d' is %d\n", a, 1 << a);
   }

   return 0;
}

You'll find lots of examples in C that use bit masks in operations, usually to set options.

Structures and type definitions

Throughout this series, we've used the standard C variable types like int and char and float. These work well for most applications. But sometimes, it can be useful to combine several variables together into a new kind of variable. And C provides a mechanism to do this, called a structure.

Defining a structure involves the struct keyword. Enclose the components of the structure in curly braces, just as you would define other variables in a program. After the curly braces, you can name the variable that should use this structure.

Structures allow you to group together related values in a program. For example, if you were writing a program that used complex numbers, you might define a structure to contain the real and imaginary parts of the complex value. Or if you were writing a system that used coordinates, you might create a structure that paired the 𝓍 and 𝓎 values together.

#include <stdio.h>

int
main()
{
   struct {
      float x;
      float y;
   } loc;

   loc.x = 10.0;
   loc.y = 1.5;

   /* display the coordinate */

   printf("the x,y coordinate is %f,%f\n", loc.x, loc.y);

   return 0;
}

But when you need a structure, it's probably easier to create some kind of alias to the structure, so you don't have to keep typing the definition of the structure—as you would have to do if you passed a structure between functions. In C, an alias for a variable is called a type definition. The usage is typedef variabletype newvariabletype;. For example, if you wanted to create an alias for a new "variable type" that would store only Yes and No values, you might create a type definition for a boolean variable like this:

typedef short boolean;

Or to create an alias for a structure, you would type:

typedef struct {
   float x;
   float y;
} coord_t;

Once you've made that type definition, you can just use coord_t wherever you would have had to write the full structure definition. You can treat coord_t like it was any regular variable.

Using structures and type definitions can greatly simplify your code, making it easier to read:

#include <stdio.h>

typedef struct {
   float x;
   float y;
} coord_t;

typedef short boolean;
#define TRUE 1
#define FALSE 0

int
main()
{
   boolean istrue;
   coord_t loc;

   loc.x = 10.0;
   loc.y = 1.5;

   /* display the coordinate */

   printf("the x,y coordinate is %f,%f\n", loc.x, loc.y);

   /* test the boolean */

   istrue = TRUE;

   if (istrue) {
      puts("yes, it's true");
   }

   return 0;
}

Sorting

We've learned a lot about how to define arrays, resize them, and otherwise manipulate them. These basic array actions can get us very far down the road in our programming. But there's another array manipulation that lends even greater power: sorting.

When you store data in an array, you might not be able to guarantee that each entry is entered in numerical order. Even if you create the array so that all stored values are stored in increasing order, you might later update some of those values, and need to put the array back into numerical order. And to do that, you need to know how to sort.

You can find lots of examples on the Internet about different sorting algorithms. Some methods are very slow, like Bubble Sort. Other methods can be very fast! And depending on what kinds of things you need to sort, some methods might be slightly faster than others. One sorting method that runs efficiently for a variety of data is the Quick Sort, implemented as qsort in C. I won't try to explain how Quick Sort operates in this guide, but know that qsort sorts an array.

To use qsort to sort an array, you need to tell qsort what array to work on, how many elements are in the array, how big each element is, and how to compare any two values. We've seen how to do most of that already. For example, allocating memory with malloc requires passing a combination of "how many" and "how big is each."

But why do you need to tell qsort how to compare two elements?

If qsort only sorted numbers, you might not have to tell it how to compare two numbers. But qsort can sort arrays made of up things that aren't just numbers. For example, you can create an array of a structure. In that case, how would qsort know how to compare two elements? Which element in the structure should it use for sorting?

That's why when you use qsort you also need to give it a function that it will use to compare two values. You do that by passing a pointer to a function. (That means you'll add a * in the function argument, to make a pointer.)

Let's write an example program to demonstrate how to use qsort to sort a list of numbers. To use qsort, we first need to define a comparison function. This should return a negative number if the first value is less than the second, a positive value if the first value is greater than the second, or zero if they are equal.

#include <stdio.h>
#include <stdlib.h>

#define ARRAY_SIZE 10

int
compare_num(const void *a, const void *b)
{
   int a1, b1;

   a1 = *(int *) a;
   b1 = *(int *) b;

   if (a1 < b1) {
      return -1;
   }
   else if (a1 > b1) {
      return 1;
   }
   else {
      return 0;
   }
}

int
main()
{
   int array[ARRAY_SIZE];
   int i;

   /* randomize the array */

   srand(13372);                       /* my random seed */

   for (i = 0; i < ARRAY_SIZE; i++) {
      array[i] = (int) random() % 100;
   }

   /* print the array */

   puts("before sorting:");

   for (i = 0; i < ARRAY_SIZE; i++) {
      printf("%d ", array[i]);
   }

   putchar('\n');

   /* sort the array */

   qsort(array, ARRAY_SIZE, sizeof(int), *compare_num);

   /* print the array */

   puts("after sorting:");

   for (i = 0; i < ARRAY_SIZE; i++) {
      printf("%d ", array[i]);
   }

   putchar('\n');

   /* done */

   return 0;
}

I've shown the comparison with an explicit if-else block, but you could instead return the difference of the two values. If you passed 3 and 5 as the two values, you could return the difference as 3 − 5 (which is -2). Or if you passed 9 and 1 as the two values, 9 − 1 would be positive (that's 8). Two equal values like 2 and 2 would be 2 − 2 (which is zero).

PRACTICE

Practice program 1.

Write a function that shows the binary representation of a number. Use a sample program to iterate from 0 to 8, to show each value in its binary form.

Practice program 2.

Write a function that adds two vectors, where each vector has an 𝓍 and 𝓎 component. To add two vectors, simply add the 𝓍 values together, and the 𝓎 values together. That is, vector 2,2 plus vector 1,3 equals vector 4,5. Use a sample program to test this function.

Practice program 3.

Write a function that multiplies two complex numbers. In mathematics, a complex number is represented as 𝓍+𝔦𝓎, where 𝔦 is the square root of -1. For two complex numbers 𝓍1+𝔦𝓎1 and 𝓍2+𝔦𝓎2, the product is:

Practice program 4.

Write a sample program that shuffles a deck of cards. Let's keep this simple, and use a special deck of only ten cards. Each card is just a value from zero to nine (or zero to ninety, if you want to multiply each by ten to get a more obvious number to work with). This is a neat example of how to shuffle a deck of cards through sorting. Hint: use a structure that has a cardvalue and shuffle element, and assign a random number to each shuffle value. Sort on the shuffle.

Need help? Check out the sample solutions.