An Exclusive

In addition to && and ||, which are “logical operators,” C also supports & and |, which are “bitwise operators,” which is to say that they operate on individual bits. If a is a bit and b is a bit, then the value of a & b, pronounced “a AND b,” is 1 if both of a and b are 1; otherwise, the value is 0. In other words,

  • 1 & 1 is 1,
  • 1 & 0 is 0,
  • 0 & 1 is 0, and
  • 0 & 0 is 0.

Meanwhile, the value of a | b, pronounced “a OR b,” is 1 if either or both of a and b are 1; otherwise, the value is 0. In other words,

  • 1 | 1 is 1,
  • 1 | 0 is 1,
  • 0 | 1 is 1, and
  • 0 | 0 is 0.

C also supports ^, whereby the value of a ^ b, pronounced “a XOR b,” is 1 if exactly one of a and b is 1; otherwise, the value is 0. In other words,

  • 1 ^ 1 is 0,
  • 1 ^ 0 is 1,
  • 0 ^ 1 is 1, and
  • 0 ^ 0 is 0.

Of course, C doesn’t have a type for single bits, so these bitwise operators actually operate on multi-bit values “bitwise,” bit for bit, left to right (or, equivalently, right to left). For instance, if a is a 32-bit int with a value of 5 and b is a 32-bit int with a value of 6, then a & b is 4 because:

  00000000000000000000000000000101
& 00000000000000000000000000000110
  --------------------------------
  00000000000000000000000000000100

Meanwhile, a | b would be 7 because:

  00000000000000000000000000000101
| 00000000000000000000000000000110
  --------------------------------
  00000000000000000000000000000111

And a ^ b would be 3 because:

  00000000000000000000000000000101
^ 00000000000000000000000000000110
  --------------------------------
  00000000000000000000000000000011

Among these operators, XOR is perhaps the most powerful.

Crypto

XOR can be used to encrypt messages! Suppose that you want to say hello to someone securely, without anyone else knowing. Thanks to ASCII, a message like HI can be represented in decimal as 72 73 or equivalently in binary as 01001000 01001001. If you and that someone agree in advance on a key that’s a random sequence of 16 bits, otherwise known as a “one-time pad,” you can encrypt your message by XORing your message with it. For instance, if your one-time pad is 10101010 01010101 and your plaintext is HI, then your ciphertext would be 11100010 00011100 because:

  01001000 01001001
^ 10101010 01010101
  -----------------
  11100010 00011100

  1. (1 point.) Upon receipt of your ciphertext, 11100010 00011100, which bitwise operator could the recipient use to decrypt it so as to know what you said?

  2. (1 point.) Suppose that you have received ciphertext of 01100101 10100010 01101111 that you know was encrypted by someone with a one-time pad of 00111100 11100111 00111100. What three ASCII characters (in plaintext) did you receive?

  3. (2 points.) Suppose that you want to send someone a message that’s longer than HI, but you only agreed in advance on a key with 16 bits. How could you encrypt your longer message nonetheless, without having to agree on a new key altogether?

  4. (2 points.) Why would it be better to agree somehow on a new, longer key instead?

Variables

XOR can also be used to save space, albeit minimal! Consider the function below, which has two arguments but otherwise has no local variables.

void f(int *a, int *b)
{
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}
  1. (2 points.) If, per this function’s declaration, each of a and b is the address of an int, exactly what does this function do to *a and *b, the values at those addresses? (Consider, for instance, if *a is 1 and *b is 2.) Put another way, what would be a better name for this function than f?

Backups

XOR can also be used to back up your data! Suppose that your computer has just one drive on which to store files. If that drive were to fail, you could lose all of your data. Having a second drive with copies of your files as a backup would be better. But suppose that you have so many files that you need that second drive for more storage. Backing up both drives would seem to require two more drives for a total of four. But not so with XOR! Thanks to XOR, you can save a bit of space (and money!) by buying just one additional drive, for a total of three. But instead of storing files on that third drive, you can instead store the XOR of your other two drives. If any of those three drives fail, you can recover its bits by XORing the other two drives onto a new drive.

For the sake of discussion, suppose that these drives are not very large. They can each store, say, only 8 bits. (You should have shopped around.) Suppose that the first drive contains 11110000 and the second drive contains 00011000. You should thus store 11101000 on your third drive because:

  11110000
^ 00011000
  --------
  11101000

  1. (2 points.) Suppose that one of your three drives fails and, before you have time to XOR your remaining two drives onto a new third drive, one of your remaining two drives fails as well. What might the effect be on your files?

  2. (2 points.) Suppose that you now have not two but three hard drives with files that you’d like to back up, such that if any one of the three drives fails you’d like to be able to recover the data. How many additional drives do you minimally need? And what would you store on the additional drive(s)?