I ran into the following programming problem:

You have the following architecture: two registers, A and B, operator increment (on a register), operator decrement and operator “jump to … if a register is 0″. With these tools, given some values in A and B they should be swapped.

I immediately recalled two cute tricks:

First, a way to swap two variables w/o an intermediate, using addition and subtraction:

A <- A + B
B <- A - B
A <- A - B

After these operations, A and B will have been swapped.

Second, a way to add two numbers using ++ and –:

while (A != 0)
{
  A--;
  B++;
}

B will have the sum of A and B after the loop. Subtraction is achieved similarly.

So, I was sure these two tricks can be combined to solve the original problem. But it can’t, since when “adding” A and B in the first step of the swapping using the “inc/dec loop” techique, B gets eaten up to 0, so it’s lost.

Right now I’m thinking how this problem can be solved…

BTW, swapping can be done with XORs too (replacing + and - by XORs). Or shortly, in C++:

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

Sweet

Related posts:

1. nice solution found to that binary stream problem

This entry was posted on Wednesday, April 21st, 2004 at 12:29 am and is filed under C / C++, Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.