Branchless version of swapping x with y if x > y?

Question

Assuming x and y are signed integers, is there some super efficient trick for implementing:

if (x < y) {
    std::swap(x, y);
}

I can instantly think of a solution using c = x < y and then you assign x to c * x + (1 - c) * y etc. but this approach emits multiplication instructions, which I would like to avoid. Is there a way to do this with bit fiddling alone?

EDIT: Just clarifying that what I really care about is trying to get rid of the branch caused by the if. In other words, I'm aware of the XOR trick to do a swap, but that's not what I'm asking.

Answer 1

I not sure, is this speedp your code, but this is branchless solution:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  int a = atoi(argv[1]);
  int b = atoi(argv[2]);
  int c = a - b;
  c &= c >> 31; // SXT for signed int
  a -= c;
  b += c;
  printf("Result: %d %d\n", a, b);
}

Answer 2

In case x and y are written to memory after this operation then you might be able to use write to dynamic memory location instead of conditional jump. For example to sort a[0], a[1]:

int x = a[0];
int y = a[1];
a[x >= y] = x;
a[y > x] = y;

If you need to read the values back immediately, then it will likely be slower than even predictable branch, but it might depend on processor.