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).

Why do you ask if there is a solution without an if statement or any other "conditional" code path? — Progman
– Progman, Commented Oct 1 at 16:23
From your explanation of your requirements, it sounds like you could just drop the if-block and use the else-block in all cases. If you can't do that, then, can you add more information about the requirements that preclude that? — ruakh
– ruakh, Commented Oct 1 at 17:05
Since you're doing this for a range of j and k, it must be that there's a loop. You could take the "if k == 1" part outside the loop, or put it in a separate loop. I think. I don't know what the entire function is meant to do, so I can't really comment on how to simplify it. What's it for? — Topological Sort
– Topological Sort, Commented Oct 1 at 18:24

Kelly Bundy · Accepted Answer · 2025-10-06 16:15:18Z

6

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.

edited Oct 6 at 16:15

answered Oct 6 at 10:36

Kelly Bundy

28k7 gold badges34 silver badges76 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

maraca · Accepted Answer · 2025-10-06 12:30:32Z

4

First lets rewrite the algorithm as two swaps:

swap 0 with a
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).

edited Oct 6 at 12:30

answered Oct 6 at 10:41

maraca

9,5873 gold badges27 silver badges50 bronze badges

2 Comments

maraca Oct 6 at 10:44

I guess it is overkill but it shows how we can get rid of branching in general for integer comparisons.

The Lost Petrol Oct 8 at 19:10

This also checks out, but, since it involves strictly more code and run time than @Kelly Bundy's solution, not to mention the conspicuous "31", you will of course understand if I use Kelly's algorithm rather than yours. Thank you.

fana · Accepted Answer · 2025-10-02 03:01:04Z

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.)

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related