Обмен двух переменных без использования третьей переменной
Один из очень сложных вопросов, заданных в интервью.
Поменяйте местами значения двух переменных, например a=10 а также b=15,
Как правило, чтобы поменять местами две переменные, нам нужна третья переменная, например:
temp=a;
a=b;
b=temp;
Теперь необходимо поменять значения двух переменных без использования третьей переменной.
32 ответа
Использование алгоритма обмена xor
void xorSwap (int* x, int* y) {
if (x != y) { //ensure that memory locations are different
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
Почему тест?
Тест должен гарантировать, что x и y имеют разные области памяти (а не разные значения). Это потому что (p xor p) = 0 и если оба x и y совместно используют одну и ту же ячейку памяти, когда для одного установлено значение 0, оба равны 0. Когда оба значения *x и *y равны 0, все другие операции xor на *x и *y будут равны 0 (как они одинаковы), что означает, что функция установит для * * и *y значение 0.
Если они имеют одинаковые значения, но не одну и ту же ячейку памяти, все работает как положено
*x = 0011
*y = 0011
//Note, x and y do not share an address. x != y
*x = *x xor *y //*x = 0011 xor 0011
//So *x is 0000
*y = *x xor *y //*y = 0000 xor 0011
//So *y is 0011
*x = *x xor *y //*x = 0000 xor 0011
//So *x is 0011
Должно ли это быть использовано?
В общем случае нет. Компилятор оптимизирует временную переменную и, учитывая, что замена является обычной процедурой, он должен вывести оптимальный машинный код для вашей платформы.
Возьмем, к примеру, эту программу быстрого тестирования, написанную на C.
#include <stdlib.h>
#include <math.h>
#define USE_XOR
void xorSwap(int* x, int *y){
if ( x != y ){
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
void tempSwap(int* x, int* y){
int t;
t = *y;
*y = *x;
*x = t;
}
int main(int argc, char* argv[]){
int x = 4;
int y = 5;
int z = pow(2,28);
while ( z-- ){
# ifdef USE_XOR
xorSwap(&x,&y);
# else
tempSwap(&x, &y);
# endif
}
return x + y;
}
Скомпилировано с использованием:
gcc -Os main.c -o swap
XOR версия занимает
real 0m2.068s
user 0m2.048s
sys 0m0.000s
Где, как версия с временной переменной принимает:
real 0m0.543s
user 0m0.540s
sys 0m0.000s
Общая форма:
A = A operation B
B = A inverse-operation B
A = A inverse-operation B
тем не менее, вы должны следить за переполнением, а также не все операции имеют обратное значение, которое четко определено для всех значений, которые определены для операции. например, * и / работают, пока A или B не станут 0
xor особенно приятен, так как он определен для всех целых и является его собственным обратным
Никто не предложил использовать std::swap, еще.
std::swap(a, b);
Я не использую никаких временных переменных и в зависимости от типа a а также b реализация может иметь специализацию, которая также не имеет. Реализация должна быть написана, зная, подходит ли "трюк" или нет. Нет смысла пытаться угадать.
В целом, я бы, вероятно, хотел сделать что-то подобное, так как это будет работать для типов классов, позволяя ADL найти лучшую перегрузку, если это возможно.
using std::swap;
swap(a, b);
Конечно, реакция интервьюера на этот ответ может многое сказать о вакансии.
Как уже отмечалось в manu, алгоритм XOR является популярным, который работает для всех целочисленных значений (включая указатели, с некоторой удачей и приведением). Для полноты картины хотелось бы упомянуть еще один менее мощный алгоритм с сложением / вычитанием:
A = A + B
B = A - B
A = A - B
Здесь вы должны быть осторожны с переполнением / потерей, но в остальном все работает так же хорошо. Вы можете даже попробовать это на float /doubles в случае, если XOR не разрешен для них.
Глупые вопросы заслуживают соответствующих ответов:
void sw2ap(int& a, int& b) {
register int temp = a; // !
a = b;
b = temp;
}
Единственное хорошее использование register ключевое слово.
Поменяйте местами два числа, используя третью переменную, вот так:
int temp;
int a=10;
int b=20;
temp = a;
a = b;
b = temp;
printf ("Value of a", %a);
printf ("Value of b", %b);
Обмен двух чисел без использования третьей переменной
int a = 10;
int b = 20;
a = a+b;
b = a-b;
a = a-b;
printf ("value of a=", %a);
printf ("value of b=", %b);
Конечно, ответ C++ должен быть std::swap,
Тем не менее, в следующей реализации swap:
template <typename T>
void swap (T &a, T &b) {
std::pair<T &, T &>(a, b) = std::make_pair(b, a);
}
Или, как однострочник:
std::make_pair(std::ref(a), std::ref(b)) = std::make_pair(b, a);
Вот еще одно решение, но один риск.
код:
#include <iostream>
#include <conio.h>
void main()
{
int a =10 , b =45;
*(&a+1 ) = a;
a =b;
b =*(&a +1);
}
любое значение в местоположении а +1 будет переопределено.
#include<iostream.h>
#include<conio.h>
void main()
{
int a,b;
clrscr();
cout<<"\n==========Vikas==========";
cout<<"\n\nEnter the two no=:";
cin>>a>>b;
cout<<"\na"<<a<<"\nb"<<b;
a=a+b;
b=a-b;
a=a-b;
cout<<"\n\na="<<a<<"\nb="<<b;
getch();
}
Давайте посмотрим на простой пример c для замены двух чисел без использования третьей переменной.
программа 1:
#include<stdio.h>
#include<conio.h>
main()
{
int a=10, b=20;
clrscr();
printf("Before swap a=%d b=%d",a,b);
a=a+b;//a=30 (10+20)
b=a-b;//b=10 (30-20)
a=a-b;//a=20 (30-10)
printf("\nAfter swap a=%d b=%d",a,b);
getch();
}
Выход:
До обмена а =10 б =20 После обмена а =20 б =10
Программа 2: Использование * и /
Давайте посмотрим на другой пример, чтобы поменять местами два числа, используя * и /.
#include<stdio.h>
#include<conio.h>
main()
{
int a=10, b=20;
clrscr();
printf("Before swap a=%d b=%d",a,b);
a=a*b;//a=200 (10*20)
b=a/b;//b=10 (200/20)
a=a/b;//a=20 (200/10)
printf("\nAfter swap a=%d b=%d",a,b);
getch();
}
Выход:
До обмена а =10 б =20 После обмена а =20 б =10
Программа 3: Использование побитового оператора XOR:
Побитовый оператор XOR можно использовать для замены двух переменных. XOR двух чисел x и y возвращает число, в котором все биты равны 1, где биты x и y различаются. Например, XOR 10 (в двоичном 1010) и 5 (в двоичном 0101) равно 1111, а XOR 7 (0111) и 5 (0101) равно (0010).
#include <stdio.h>
int main()
{
int x = 10, y = 5;
// Code to swap 'x' (1010) and 'y' (0101)
x = x ^ y; // x now becomes 15 (1111)
y = x ^ y; // y becomes 10 (1010)
x = x ^ y; // x becomes 5 (0101)
printf("After Swapping: x = %d, y = %d", x, y);
return 0;
Выход:
После замены: x = 5, y = 10
Программа 4:
Никто еще не предложил использовать std::swap.
std::swap(a, b);
Я не использую никаких временных переменных и в зависимости от типа a и b реализация может иметь специализацию, которая тоже не имеет. Реализация должна быть написана, зная, подходит ли "трюк" или нет.
Проблемы с вышеуказанными методами:
1) Подход, основанный на умножении и делении, не работает, если одно из чисел равно 0, так как произведение становится равным 0 независимо от другого числа.
2) Оба арифметических решения могут вызвать арифметическое переполнение. Если x и y слишком велики, сложение и умножение могут выходить за пределы целочисленного диапазона.
3) Когда мы используем указатели на переменные и выполняем обмен функций, все вышеперечисленные методы не работают, когда оба указателя указывают на одну и ту же переменную. Давайте посмотрим, что произойдет в этом случае, если оба будут указывать на одну и ту же переменную.
// Битовый метод на основе XOR
x = x ^ x; // x becomes 0
x = x ^ x; // x remains 0
x = x ^ x; // x remains 0
// Арифметический метод
x = x + x; // x becomes 2x
x = x – x; // x becomes 0
x = x – x; // x remains 0
Давайте посмотрим на следующую программу.
#include <stdio.h>
void swap(int *xp, int *yp)
{
*xp = *xp ^ *yp;
*yp = *xp ^ *yp;
*xp = *xp ^ *yp;
}
int main()
{
int x = 10;
swap(&x, &x);
printf("After swap(&x, &x): x = %d", x);
return 0;
}
Выход:
После обмена (&x, &x): x = 0
Обмен переменной с самим собой может потребоваться во многих стандартных алгоритмах. Например, посмотрите эту реализацию QuickSort, где мы можем поменять переменную с собой. Вышеупомянутой проблемы можно избежать, поставив условие перед заменой.
#include <stdio.h>
void swap(int *xp, int *yp)
{
if (xp == yp) // Check if the two addresses are same
return;
*xp = *xp + *yp;
*yp = *xp - *yp;
*xp = *xp - *yp;
}
int main()
{
int x = 10;
swap(&x, &x);
printf("After swap(&x, &x): x = %d", x);
return 0;
}
Выход:
После обмена (&x, &x): x = 10
Так как оригинальным решением является:
temp = x; y = x; x = temp;
Вы можете сделать его двухслойным, используя:
temp = x; y = y + temp -(x=y);
Тогда сделайте это одним вкладышем, используя:
x = x + y -(y=x);
Рассматривать a=10, b=15:
Использование сложения и вычитания
a = a + b //a=25
b = a - b //b=10
a = a - b //a=15
Использование деления и умножения
a = a * b //a=150
b = a / b //b=10
a = a / b //a=15
Если вы немного измените вопрос о двух регистрах сборки вместо переменных, вы также можете использовать xchg операция как одна опция, и операция стека как другая.
#include <iostream>
using namespace std;
int main(void)
{
int a,b;
cout<<"Enter a integer" <<endl;
cin>>a;
cout<<"\n Enter b integer"<<endl;
cin>>b;
a = a^b;
b = a^b;
a = a^b;
cout<<" a= "<<a <<" b="<<b<<endl;
return 0;
}
Обновление: в этом мы принимаем ввод двух целых чисел от пользователя. Затем мы используем побитовую операцию XOR, чтобы поменять их местами.
Скажем, у нас есть два целых числа a=4 а также b=9 а потом:
a=a^b --> 13=4^9
b=a^b --> 4=13^9
a=a^b --> 9=13^9
Как насчет того, если мы займемся параллельной обработкой с языком "GO" ..
var x = 100; var y = 200;
swap1:= func(var i) {x = i}swap2:= func(var y) {y = i} Распараллелить (swap1, swap2)
Лучший ответ - использовать XOR и использовать его в одной строке.
(x ^= y), (y ^= x), (x ^= y);
x, y - переменные, и запятая между ними вводит точки последовательности, поэтому она не становится зависимой от компилятора. Ура!
В
awk, без необходимости временной переменной, временного массива, вызова внешней функции, подстроки их значений друг из друга, операций XOR или даже любых математических операций любого рода,
этот трюк работает для того, являются ли их значения числовыми, строковыми или даже произвольными байтами, которые не совместимы с UTF8, и типы двух переменных даже не должны совпадать:
gawk/mawk/nawk '{
a = (b) \
substr("", ( b = (a) )^"")
}'
Даже в Unicode-locale,
gawkрежим юникода может поменять местами значения
arbitrary non-UTF8 bytesбез каких-либо сообщений об ошибках.
Нет необходимости использовать локаль C или POSIX.
Почему это работает, так это то, что в процессе этой конкатенации исходное значение уже было помещено в некоторую внутреннюю промежуточную площадку системы, поэтому последующее
assignment of b's value into aне оказывает никакого влияния на то, что назначается в
Вторая половина берет подстроку пустой строки, поэтому, конечно, ничего не выходит и не влияет на первую половину.
После
b = a, я сразу беру его в нулевой степени, что всегда возвращает 1 в awk
поэтому последняя часть становится
# in awk, string indices start from 1 not 0
substr(EMPTY_STRING, STARTING-POSITION-OF-ONE)
конечно, из этого ничего не выходит, что является желаемым эффектом, поэтому чистое исходное значение может быть присвоено в .
Это не принимает подстроку значения 's или '. Он использует свойства динамической типизации awk.
Подход на основе XOR, который очищает, по-прежнему требует 3 операций, а также проверку безопасности на позицию памяти (для C). А для gnu-awk это
xor()функция работает только с неотрицательными числовыми входными данными.
Этот однострочный подход позволяет обойти все распространенные проблемы с заменой значений.
Либо
aили же
b, или даже то и другое, будучи ячейкой массива, независимо от того, одномерное или многомерное, например
arr[ _pos_idx_a_ ]
работает точно так же с этим однострочным подходом. Единственное ограничение, о котором я мог подумать, заключается в том, что этот подход не может напрямую поменять местами полное содержимое всего массива с другим массивом.
Я думал добавить проверку для a==b, чтобы избежать двойного присваивания, но потом понял, что внутренние системные ресурсы, необходимые для выполнения такой проверки, не стоят крошечного количества сэкономленного времени.
Это правильный алгоритм обмена XOR
void xorSwap (int* x, int* y) {
if (x != y) { //ensure that memory locations are different
if (*x != *y) { //ensure that values are different
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
}
Вы должны убедиться, что места в памяти разные, а также что фактические значения разные, потому что A XOR A = 0
Вы можете сделать.... простым способом... в одной строке Логика
#include <stdio.h>
int main()
{
int a, b;
printf("Enter A :");
scanf("%d",&a);
printf("Enter B :");
scanf("%d",&b);
int a = 1,b = 2;
a=a^b^(b=a);
printf("\nValue of A=%d B=%d ",a,b);
return 1;
}
или же
#include <stdio.h>
int main()
{
int a, b;
printf("Enter A :");
scanf("%d",&a);
printf("Enter B :");
scanf("%d",&b);
int a = 1,b = 2;
a=a+b-(b=a);
printf("\nValue of A=%d B=%d ",a,b);
return 1;
}
Вы могли бы сделать:
std::tie(x, y) = std::make_pair(y, x);
Или используйте make_tuple при замене более двух переменных:
std::tie(x, y, z) = std::make_tuple(y, z, x);
Но я не уверен, использует ли внутренне std::tie временную переменную или нет!
В R отсутствует параллельное назначение, предложенное Эдсгером В. Дейкстрой в "Дисциплина программирования", 1976, глава 4, стр.29. Это позволило бы найти элегантное решение:
a, b <- b, a # swap
a, b, c <- c, a, b # rotate right
Я думаю, что std::exchange можно использовать из C++14.
int a = 8;
int b = 10;
std::cout << a << " " << b << std::endl;
//Returns b and Replaces b with a.
a = std::exchange(b, a);
std::cout << a << " " << b << std::endl;
#include <stdio.h>
int main()
{
int a, b;
printf("Enter A :");
scanf("%d",&a);
printf("Enter B :");
scanf("%d",&b);
a ^= b;
b ^= a;
a ^= b;
printf("\nValue of A=%d B=%d ",a,b);
return 1;
}
В JavaScript:
function swapInPlace(obj) {
obj.x ^= obj.y
obj.y ^= obj.x
obj.x ^= obj.y
}
function swap(obj) {
let temp = obj.x
obj.x = obj.y
obj.y = temp
}
Будьте в курсе времени выполнения обоих вариантов.
Запустив этот код, я измерил его.
console.time('swapInPlace')
swapInPlace({x:1, y:2})
console.timeEnd('swapInPlace') // swapInPlace: 0.056884765625ms
console.time('swap')
swap({x:3, y:6})
console.timeEnd('swap') // swap: 0.01416015625ms
Как вы можете видеть (и как уже говорили многие), замена на месте (xor) занимает больше времени, чем другой вариант, использующий переменную temp.
public void swapnumber(int a,int b){
a = a+b-(b=a);
System.out.println("a = "+a +" b= "+b);
}
Может быть, не по теме, но если вы знаете, что вы меняете одну переменную между двумя разными значениями, вы можете сделать логику массива. Каждый раз, когда запускается эта строка кода, она меняет значение между 1 и 2.
n = [2, 1][n - 1]
Попробуйте этот код: (пример в php)
$a = 5;
$b = 7;
echo $a .' ***Before*** '. $b;
$a = $a + $b; //12
$b = $a - $b; //12 - 7 = 5
$a = $a - $b; //12 - 5 = 7
echo $a .' ***After*** '. $b;
a = a + b - (b=a);
Это очень просто, но может вызвать предупреждение.