Один из очень сложных вопросов, заданных в интервью.
Поменяйте значения двух переменных, таких как a=10 и b=15.
Обычно для замены двух значений переменных нам нужна третья переменная типа:
temp=a;
a=b;
b=temp;
Теперь требование - значения swap двух переменных без использования третьей переменной.
Используя xor swap algorithm
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 (так же, как они совпадают), что означает, что функция будет устанавливать оба * x и * 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 особенно приятен, поскольку он определен для всех int и является его собственным обратным
a = a + b
b = a - b // b = a
a = a - b
Никто не предложил использовать 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.
Вы посмотрели алгоритм обмена XOR?
#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();
}
Вот еще одно решение, но один риск.
код:
#include <iostream>
#include <conio.h>
void main()
{
int a =10 , b =45;
*(&a+1 ) = a;
a =b;
b =*(&a +1);
}
любое значение в местоположении a + 1 будет переопределено.
Поскольку исходное решение:
temp = x; y = x; x = temp;
Вы можете сделать это двумя лайнерами, используя:
temp = x; y = y + temp -(x=y);
Затем сделайте его одним лайнером, используя:
x = x + y -(y=x);
Если вы немного измените вопрос о двух регистрах сборки вместо переменных, вы можете использовать также операцию xchg как один параметр, а операцию стека - как еще одну.
Рассмотрим 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
#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
Конечно, ответ 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);
Поменяйте местами два числа, используя третью переменную, вот так:
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);
#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;
}
что правильный алгоритм замены 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;
}
public void swapnumber(int a,int b){
a = a+b-(b=a);
System.out.println("a = "+a +" b= "+b);
}
Посмотрим простой пример 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();
}
Вывод:
Перед заменой a = 10 b = 20 После замены a = 20 b = 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();
}
Вывод:
Перед заменой a = 10 b = 20 После замены a = 20 b = 10
Программа 3: Использование побитового оператора XOR:
Побитовый оператор XOR может использоваться для замены двух переменных. XOR двух чисел x и y возвращает число, которое имеет все биты как 1, где бит x и y различаются. Например, XOR 10 (In Binary 1010) и 5 (In Binary 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) Когда мы используем указатели на переменную и выполняем функцию swap, все вышеперечисленные методы терпят неудачу, когда оба указателя указывают на одну и ту же переменную. Давайте посмотрим, что произойдет в этом случае, если обе указывают на одну и ту же переменную.
//Побитовый метод на основе 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
Лучшим ответом было бы использовать XOR, и использовать его в одной строке было бы круто.
(x ^= y), (y ^= x), (x ^= y);
x, y - переменные, а запятая между ними вводит точки последовательности, поэтому она не становится зависимой от компилятора. Ура!
Может быть, не по теме, но если вы знаете, что вы меняете одну переменную между двумя разными значениями, вы можете сделать логику массива. Каждый раз, когда запускается эта строка кода, она меняет значение между 1 и 2.
n = [2, 1][n - 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 временную переменную или нет!
В 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) занимает больше времени, чем другой вариант с временной переменной.
a = a + b - (b=a);
Это очень просто, но может вызвать предупреждение.
однострочное решение для замены двух значений на языке c.
a=(b=(a=a+b,a-b),a-b);
second_value -= first_value;
first_value += second_value;
second_value -= first_value;
second_value *= -1;