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


Comments

comments powered by Disqus