Some time ago, I wrote about well-known trick for a two-value exchange using no intermediate variables. It’s a fun party-trick, but unless you’re working with an unusually constrained embedded project, it’s unlikely that you would ever really need to use it. On the other hand, hidden within that little trick is some real memory-conserving magic.
To recall the lesson from the previous article, two values can be exchanged through a series of three exclusive-OR assignments:
1. a = a XOR b
2. b = b XOR a
3. a = a XOR b
or in C shorthand, a ^= b^= a ^= b;
Since XOR is a fast native instruction for most microprocessors and micro-controllers, and we are only dealing with two variables, which permits pure register-based operations, this exchange can be extremely efficient. Of course, if you have a third register available, which is most often the case, then an intermediate variable may provide slightly better performance. With the recap behind us, let’s take a look at where this technique might give us some real leverage.
First, notice that XOR is commutative; a XOR b is the same as b XOR a. So the above steps can also be expressed as:
1. a = a XOR b
2. b = a XOR b
3. a = a XOR b
Furthermore, let’s introduce a third variable, just to aid in the understanding of the algorithm:
1. c = a XOR b
2. b = c XOR b
3. a = c XOR a
Notice that after step two, the values stored in a and b are equal, so we can replace step three with:
3. a = c XOR b
It is this equivalence that permits a to be used in place of c in the original algorithm.
So, as you can see, step one encodes the two values into a single variable, whereas the remaining two steps perform the decode/swap. The meat of the method is that you can store two values in a single variable, and extract either value if you know the other. How might you make use of this technique to a very productive end?
In software development, linked lists are a frequently used mechanism. These lists may be quite large, and they can become quite expensive in terms of memory consumed. Too often, the contents of such a list consume less memory than the pointers used to implement it. In embedded development, memory constraints may force us to forgo the luxury of doubly-linked lists, and rely instead on multiple traversals of singly-linked lists; or use other poorly performing techniques.
Now consider a doubly-linked list, implemented with virtually the same memory overhead as a singly linked list. How might this work? Imagine that instead of just containing a next, each link contained next XOR prev. As we traverse this list, we simply need to keep track of our most recently visited node (from), the current node, and what direction (prev or next) we moved to get from from to current. We’ll call the structure that maintains this information the cursor. As an example, assume the following 5-item list as a starting point:
| Location | Link | Remark |
|---|---|---|
| 0×7777 | 0×3333 | next XOR NULL |
| 0×3333 | 0xFFFF | prev XOR next |
| 0×8888 | 0×2222 | prev XOR next |
| 0×1111 | 0xEEEE | prev XOR next |
| 0×6666 | 0×1111 | prev XOR NULL |
Also assume these starting values for the cursor:
//Example of cursor values (and link) cursor.from = 0x3333; // cursor.from->link = 0xFFFF; cursor.current = 0x8888; // cursor.current->link = 0x2222; cursor.traversalDirection = NEXT;
This means that next is stored virtually as from XOR current->link, while prev is held directly in from. The opposite would be true if the traversalDirection was PREV. In either case we have simple access to both next and prev. Given the values above, we can see that next is located at 0×1111.
If we would like to return to the prev (i.e. reverse direction), we already have the address stored in cursor.from, so the algorithm is simply:
// Traverse to next using fast exchange (C shorthand)... cursor.current ^= cursor.from ^= cursor.current ^= cursor.from; // ...then set the direction. cursor.traversalDirection = PREV; // The resulting values for cursor are: cursor.from = 0x8888; cursor.current = 0x3333; cursor.traversalDirection = PREV;
If instead, we wish to advance our cursor to the next element, (i.e. continue in the same direction), it is only slightly different:
// Traverse to previous using fast exchange... cursor.current ^= cursor.from ^= cursor.current ^= cursor.from; // ...then XOR with link to advance. cursor.current ^= cursor.from->link; // The resulting values for cursor are: cursor.from = 0x8888; cursor.current = 0x1111; cursor.traversalDirection = NEXT;
You can try this for yourself using the other node values given. Of course, as with ordinary list traversals, checks must be done to detect the start and end of the list (except for ring-lists). Node insertion and removal aren’t much more complex than traversal, and I have the utmost confidence that you can figure them out on your own.
This but one very useful application of the fast exchange in significantly reducing memory consumption for a doubly linked list.
Have you discovered other applications for the fast exchange? I’d like to hear your 2 cents!
Comments