Magic

C has been around for a long time, and, correspondingly, so have C programmers. Unfortunately, crufty old C programmers can be a little more clever than is strictly necessary; thus were born some of the tricks and hacks listed below. Aside from their novelty value, these hacks are worth your time to study because doing so will vastly increase your understanding of the C language. Also, professional interviewers love to ask questions like these.

Note: Don't use these in your code! With an optimizing compiler, there's no benefit to writing code like this anymore. Doing so will only make your code unmaintainable, and probably cost you marks for unreadability. On a modern processor it'll probably be slower, too.

XOR swap

This one in particular is a recurring favorite of interviewers. The following function swaps two integer values without using an intermediate variable:

void swap(int *a, int *b) {
  *a ^= *b;
  *b ^= *a;
  *a ^= *b;
}

How does this work? Well, the XOR (^) operator has some nice properties: it's commutative (A^B = B^A), associative (A^(B^C) = (A^B)^C), and has an identity function (A^0 = A) (If you've had an algebraic structures course you'll notice that XOR defines an Abelian group. Props for being an over-achiever). Basically, when we overwrite A with A = A^B, we can later extract the original value of A by XORing it with B again, since (A^B)^B = A^(B^B) = A^0 = A. Likewise for B, once we've extracted A. Wikipedia has a rather nice version of this proof, if you're interested.

Duff's Device

This one is even more fun. In C, if you have a case statement that doesn't end in a break control will "fall through" into the next case statement, i.e:

switch(foo) {
  case 0: do_something();
  case 1: do_something_else();
}

will execute do_something() and do_something_else() if foo = 0. That's sort of odd, yeah -- but it lets you do all kinds of nifty hacks. For example, the (in)famous Duff's Device:

char *to, *from;
int count;
{
  int n = (count + 7) / 8;
  switch (count % 8) {
  case 0: do { *to++ = *from++;
  case 7:      *to++ = *from++;
  case 6:      *to++ = *from++;
  case 5:      *to++ = *from++;
  case 4:      *to++ = *from++;
  case 3:      *to++ = *from++;
  case 2:      *to++ = *from++;
  case 1:      *to++ = *from++;
          } while (--n > 0);
  }
}

What (the hell?) does this code do? It copies count characters from *from to *to -- but only requires ceil(count/8) loop iterations to do so. It does this by copying 8 characters per loop iteration, and using the switch/case statement to handle the characters left over in the last iteration. So if we copied 18 characters, it would copy 8 in one iteration, 8 in the next, and 2 in the final. In general, this type of trick (doing multiple iterations of a loop at once) is called *loop unrolling. Again, Wikipedia has a great explanation and history.

-- TrevorFountain - 28 Jan 2009

Topic revision: r2 - 18 Feb 2009 - 17:49:15 - TrevorFountain
 
This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback
This Wiki uses Cookies