Есть ли встроенная функция подкачки в C, которая работает без использования третьей переменной?
Есть ли встроенная функция подкачки в C?
Ответы (10)
Нет.
Встроенная функция подкачки C++: swap(first,second);
Проверьте это: http://www.cplusplus.com/reference/algorithm/swap/
Вы можете использовать это, чтобы поменять местами два значения переменных без использования третьей переменной:
a=a^b;
b=a^b;
a=b^a;
Вы также можете проверить это:
Как поменять местами без третьей переменной?
c=a; a=b; b=c;
.
- person einpoklum; 08.12.2020
Почему вы не хотите использовать третью переменную? Это самый быстрый способ для подавляющего большинства архитектур.
алгоритм замены XOR работает без третьей переменной, но он проблематичен по двум причинам:
- Переменные должны быть разными, т.е.
swap(&a, &a)
не будет работать. - В целом медленнее.
Иногда может быть предпочтительнее использовать своп XOR, если использование третьей переменной приведет к сбросу стека, но обычно вы не в таком положении, чтобы сделать этот вызов.
Чтобы ответить на ваш вопрос напрямую, в стандартном C нет функции подкачки, хотя написать ее было бы тривиально.
int t = a; a = b; b = t;
против a ^= b; b ^= a; a ^= b;
. Где это потерянное время? И какая вселенная записывает своп, значительно увеличивая время, необходимое вам для решения проблемы? Это должно быть самая большая проблема, которую я когда-либо видел.
- person Peter Alexander; 14.01.2012
Предполагая, что вам нужен солотив C, а не C++, вы можете сделать его макросом, по крайней мере, используя расширение GCC, чтобы оно было достаточно общим, что-то вроде
#define SWAP(x,y) do { \
typeof(x) _x = x; \
typeof(y) _y = y; \
x = _y; \
y = _x; \
} while(0)
остерегайтесь таких уловок, как вызовы swap(t[i++],i)
; чтобы их избежать, используйте адресный оператор &
. И вам лучше использовать временное (для целых чисел есть известный и бесполезный трюк с исключающим ИЛИ).
PS: я использую две локальные переменные _x
и _y
(но я мог бы использовать только одну локальную переменную) для лучшей читабельности и, возможно, также для включения дополнительных оптимизаций компилятора.
typeof(x) _tmp = x; x = y; y = _tmp;
?
- person einpoklum; 28.07.2013
В стандарте C такой функции нет.
(В C++ используется std::swap()
.)
Возможно, вам будет полезен макрос из этого вопроса.
В C нет стандартной функции для замены двух переменных.
Макрос можно написать так:
#define SWAP(T, a, b) do { T tmp = a; a = b; b = tmp; } while (0)
и макрос можно назвать так:
int a = 42;
int b = 2718;
SWAP(int, a, b);
Следует избегать некоторых решений для написания макроса SWAP:
#define SWAP(a, b) do { a = b + a; b = a - b; a = a - b; } while (0)
когда операнды имеют знаковые типы, может произойти переполнение, а подписанное переполнение является неопределенным поведением.
Также следует избегать решения, пытающегося оптимизировать решение XOR, подобное этому:
#define SWAP(a, b) (a ^= b ^= a ^=b)
a
изменяется дважды между предыдущей и следующей точкой последовательности, поэтому это нарушает правила точек последовательности и является неопределенным поведением.
typeof(expr)
.
- person ; 28.07.2013
int
в качестве первых аргументов макроса. Теперь мы можем утверждать, что у нас есть шаблоны на нашем любимом языке :-)
- person paxdiablo; 04.07.2017
Так как вы можете скопировать любое представление объекта в беззнаковый массив символов в C, следующий макрос позволяет вам поменять местами любые два объекта:
#define SWAP(X,Y) \
do { \
unsigned char _buf[sizeof(*(X))]; \
memmove(_buf, (X), sizeof(_buf)); \
memmove((X), (Y), sizeof(_buf)); \
memmove((Y), _buf, sizeof(_buf)); \
} while (0)
В некоторых случаях GCC даже сгенерирует для этого оптимальный код. Хотя, возможно, вы не сохраните свою работу...
int x; double y;
например? :-) Возможно, вы имели в виду любые два объекта одного и того же типа.
- person paxdiablo; 04.07.2017
Есть библиотечная функция C++. Он меняет местами значения двух целочисленных переменных. Например, своп(х, у); поменяет местами значения переменных x и y. Точно так же swap(mat[i][j], mat[j][i]); поменяет местами два значения в матрице mat, а именно значение в строке i, столбце j, и значение в строке j, столбце i.
Встроенной функции подкачки нет, но вы можете попробовать это
a = a ^ b;
b = a ^ b;
a = b ^ a;
есть std::swap
т.к. вообще это зависит от вашего процессора, поддерживает ли он подкачку. есть инструкция под названием «сравнить и поменять местами», но она работает только с типами, которые помещаются в регистр и гарантированно являются атомарными. Существует встроенная реализация сравнения и подкачки (CAS) из gcc он используется для синхронизации реализаций потоков и мьютексов и, вероятно, выходит за рамки ваших целей, поэтому лучше использовать только временную переменную или, если вы действительно застряли на C, вы всегда можете использовать макрос нравится:
#define swap(a,b) a=a^b; \
b=a^b; \
a=b^a;
a
изменяется дважды между предыдущей и следующей точкой последовательности.
- person ouah; 14.01.2012
a^=b^=a^=b;
- person ouah; 14.01.2012
Я считаю, что придумал независимую от типа функцию для замены любых двух значений в стандартном C, хотя, поскольку я новичок в этом языке, я мог что-то упустить. Он использует алгоритм подкачки XOR, и я уверен, что его можно было бы еще оптимизировать, но он работает до тех пор, пока два значения указывают на одно и то же количество байтов, указанное третьим аргументом:
void swapn(void *a, void *b, size_t n) {
if (a == b) {
return;
}
size_t i;
char *x = (char *)a,
*y = (char *)b;
for (i = 0; i < n; i++) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
x++;
y++;
}
}
Пример использования:
// swap two integers
int x = 5,
y = 30;
printf("%d\t%d\n", x, y);
swapn(&x, &y, sizeof(int));
printf("%d\t%d\n\n", x, y);
// swap two floats
float a = 9.23f,
b = 6.83f;
printf("%.2f\t%.2f\n", a, b);
swapn(&a, &b, sizeof(float));
printf("%.2f\t%.2f\n\n", a, b);
// swap two doubles
double p = 4.7539,
q = 0.9841;
printf("%.4f\t%.4f\n", p, q);
swapn(&p, &q, sizeof(double));
printf("%.4f\t%.4f\n\n", p, q);
// swap two chars
char m = 'M',
n = 'n';
printf("%c\t%c\n", m, n);
swapn(&m, &n, sizeof(char));
printf("%c\t%c\n\n", m, n);
// swap two strings of equivalent length
char s[] = "Hello",
t[] = "World";
printf("%s\t%s\n", s, t);
swapn(s, t, sizeof(s));
printf("%s\t%s\n\n", s, t);
Результат:
5 30
30 5
9.23 6.83
6.83 9.23
4.7539 0.9841
0.9841 4.7539
M n
n M
Hello World
World Hello
*x
без промежуточной точки последовательности. Это легко исправить, но я не понимаю, зачем вообще нужно заморачиваться с xor swap. Это не быстрее, это не проще, это ломается, когда псевдоним двух параметров, и в этой общей реализации из двадцати строк дополнительная переменная даже не является большим кодом. Но это кажется довольно типичным агонистом, я дам вам это. n
должно быть size_t
.
- person ; 07.03.2015