Я пытался расширить xor-swap более чем на две переменные, скажемn переменные. Но я нигде не получил это лучше, чем3*(n-1).

Для двух целочисленных переменныхx1 а такжеx2 вы можете поменять их местами так:

swap(x1,x2) {
  x1 = x1 ^ x2;
  x2 = x1 ^ x2;
  x1 = x1 ^ x2;
}

Итак, предположим, у вас естьx1 ...xn со значениямиv1 ...vn, Очевидно, что вы можете «вращать» значения, последовательно применяя своп:

swap(x1,x2);
swap(x2,x3);
swap(x3,x4);
...
swap(xm,xn); // with m = n-1

Вы закончите сx1 = v2, x2 = v3...,xn = v1.

Какие расходыn-1 свопы, каждая стоимость3 Xors, оставляя нас с(n-1)*3 операцию XOR.

Более быстрый алгоритм использует только xor и присваивание, а дополнительные переменные не известны?