Swapping two array elements with two other specific array elements without using an if-statement

Question

I have an array x of n >= 4 elements, at indices 0..n-1. I want to swap the elements at indices j and k, where 0 <= k < j < n with the elements at indices 0 and 1 (it doesn't matter whether x[j] ends up at x[0] or x[1]). My question is whether there is an unconditional algorithm for doing so.

I've only been able to come up with:

if k==1
    // Exchange j with 0
    temp=x[j];
    x[j]=x[0];
    x[0]=temp;
else
    // Exchange k with 0
    temp=x[k];
    x[k]=x[0];
    x[0]=temp;
    // Exchange j with 1
    temp=x[j];
    x[j]=x[1];
    x[1]=temp;

Is there a way of doing this without an if-statement?

After the swapping, x[0] and x[1] must contain what was originally in x[j] and x[k] (in either order), and x[j] and x[k] must contain what was originally in x[0] and x[1] (in either order).

Answer 1

This works (Try it online!):

temp1 = x[0];
x[0] = x[j];
temp2 = x[k];
x[k] = temp1;
x[j] = x[1];
x[1] = temp2;

I had a hunch that it could be done with three swaps, so I tried all possibilities and found two solutions: swap j with 0, k, 1 or swap j with 1, k, 0. The above is the former but optimized to remove redundant operations.

Answer 2

First lets rewrite the algorithm as two swaps:

1. swap 0 with a
2. swap 1 with b

This is equivalent to your code if:

• k == 1: a = j, b = 1 (swap with itself, same result as no swap)
• k != 1: a = k, b = j

Assuming the numbers are integers in the two's complement we can use bit fiddling tricks to get a and b without branching:

z = k & ((k - 2) >> 31)    // 1 if k == 1,  0 otherwise
y = z - 1                  // 0 if k == 1, -1 otherwise
a = (-z & j) | (y & k)
b = z | (y & j)

z is 1 if k == 1 and 0 otherwise. We achieve this by subtracting 2 from k which makes the number negative if k is 0 or 1. The highest bit in the two's complement is set if the number is negative and after shifting by number of bits - 1 we end up with a 1 (so a 64 bit number would need to be shifted by 63). To prevent that k == 0 also becomes 1 we just do a bitwise and with k. We could already use this to create a simple solution (inverse y = 1 - z, so you have a 0 and 1 which can be used to multiply with the desired values and then adding them, the 0 always cancelling out one of the terms, e.g. a = z * j + y * k). But we can also eliminate the multiplication by using bitwise and and masks 0 and -1 (all bits set) and then bitwise or to combine the results instead of plus (because one of them is always 0).

Answer 3

Is there a way of doing this without an if-statement?

No.

"in either order" means that there are multiple possible result patterns.

There are 2 "in either order", so number of results is 4. However in this question case, the number of patterns to consider is 2. That is, swap target selection.

• (PTN1) : Swap [k] and [0], Swap [j] and [1]
• (PTN2) : Swap [k] and [1], Swap [j] and [0]

The results are not necessarily the same, and which pattern is valid depends on the inputs. So, it looks like that It is inevitable to select the pattern to be adopted based on the inputs.

(Of course, depending on the language you use, you may be able to write code that uses something other than if as a branching method, but it is not interest here.)