Brenchless conditional exchange

Author:Wojciech Muła
Added on:2010-04-08

Suppose we have to exchange (or just move) two registers A and B:

  1. C := A xor B
  2. C := 0 if condition is not true
  3. A := A xor C
  4. B := B xor C

If C is 0, then A and B left unchanged, else A and B are swapped. If only a conditional move from B to A is needed, then step 4th have to be skipped.

Here is a sample x86 code, where condition is value of CF:

sbb edx, edx ; part of step 2. - edx = 0xffffff if CF=1, 0x000000 otherwise
mov ecx, eax
xor ecx, ebx ; step 1
and ecx, edx ; completed step 2. - now C is 0 or (A xor B)
xor eax, ecx ; step 3
xor ebx, ecx ; step 4

Branchless moves are possible in Pentium Pro and higher with instructions cmovcc.

See also XOR linked list.