c++ - una - Intercambio de dos valores de variable sin usar tercera variable

que es swap en java

Question

Una de las preguntas muy complicadas que se hicieron en una entrevista.

Cambie los valores de dos variables como a=10 y b=15 .

En general, para intercambiar dos valores de variables, necesitamos una tercera variable como:

temp=a;
a=b;
b=temp;

Ahora el requisito es, intercambiar valores de dos variables sin usar la 3ª variable.

Answer 1

¿Has mirado el algoritmo de intercambio XOR ?

Answer 2

Aquí hay una solución más, pero un riesgo único.

código:

#include <iostream>
#include <conio.h>
void main()
{
int a =10 , b =45;
*(&a+1 ) = a;
a =b;
b =*(&a +1);
}

cualquier valor en la ubicación a + 1 será anulado.

Answer 3

Como ya se mencionó por manu, el algoritmo XOR es muy popular y funciona para todos los valores enteros (que incluye punteros entonces, con algo de suerte y de fundición). En aras de la exhaustividad, me gustaría mencionar otro algoritmo menos poderoso con suma / resta:

A = A + B
B = A - B
A = A - B

Aquí debe tener cuidado con los desbordamientos / subdesbordamientos, pero de lo contrario funciona igual de bien. Incluso puedes probar esto con flotadores / dobles en el caso de que XOR no esté permitido en esos.

Answer 4

Considera a=10 , b=15 :

Usando suma y resta

a = a + b //a=25
b = a - b //b=10
a = a - b //a=15

Usando división y multiplicación

a = a * b //a=150
b = a / b //b=10
a = a / b //a=15

Answer 5

Dado que la solución original es:

temp = x; y = x; x = temp;

Puedes convertirlo en un dos líneas usando:

temp = x; y = y + temp -(x=y);

Entonces hazlo un trazador de líneas usando:

x = x + y -(y=x);

Answer 6

Intercambiando dos números usando la tercera variable será así,

int temp;
int a=10;
int b=20;
temp = a;
a = b;
b = temp;
printf ("Value of a", %a);
printf ("Value of b", %b);

Intercambio de dos números sin usar tercera variable

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);

Answer 7

La mejor respuesta sería usar XOR y usarlo en una línea sería genial.

 (x ^= y), (y ^= x), (x ^= y);

x, y son variables y la coma entre ellas introduce los puntos de secuencia para que no se convierta en dependiente del compilador. ¡Aclamaciones!

Answer 8

Las preguntas estúpidas merecen respuestas apropiadas:

void sw2ap(int& a, int& b) {
register int temp = a; // !
a = b;
b = temp;
}

El único buen uso de la palabra clave register .

Answer 9

Nadie ha sugerido usar std::swap , aún.

std::swap(a, b);

No utilizo variables temporales y, dependiendo del tipo de b la implementación puede tener una especificación que tampoco. La implementación debe escribirse sabiendo si un ''truco'' es apropiado o no. No tiene sentido tratar de adivinarlo en segundo lugar.

En términos más generales, probablemente desearía hacer algo como esto, ya que funcionaría para los tipos de clase que permiten a ADL encontrar una mejor sobrecarga si es posible.

using std::swap;
swap(a, b);

Por supuesto, la reacción del entrevistador a esta respuesta podría decir mucho sobre la vacante.

Answer 10

Por supuesto, la respuesta de C ++ debe ser std::swap .

Sin embargo, tampoco hay una tercera variable en la siguiente implementación de swap :

template <typename T>
void swap (T &a, T &b) {
std::pair<T &, T &>(a, b) = std::make_pair(b, a);
}

O, como un trazador de líneas:

std::make_pair(std::ref(a), std::ref(b)) = std::make_pair(b, a);

Answer 11

Puedes hacer ... de manera fácil ... dentro de una línea Lógica

#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;
}

o

#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;
}

Answer 12

Si cambia un poco la pregunta para preguntar por 2 registros de conjunto en lugar de variables, también puede usar la operación xchg como una opción y la operación de pila como otra.

Answer 13

Tal vez fuera del tema, pero si sabe lo que está intercambiando una sola variable entre dos valores diferentes, es posible que pueda hacer una lógica de matriz. Cada vez que se ejecuta esta línea de código, cambiará el valor entre 1 y 2.

n = [2, 1][n - 1]

Answer 14

Usando el algoritmo xor swap

void xorSwap (int* x, int* y) {
if (x != y) { //ensure that memory locations are different
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}

¿Por qué la prueba?

La prueba es para asegurar que xey tengan diferentes ubicaciones de memoria (en lugar de valores diferentes). Esto es porque (p xor p) = 0 y si tanto x como y comparten la misma ubicación de memoria, cuando uno se establece en 0, ambos se establecen en 0. Cuando ambos * x y * y son 0, todas las demás operaciones xor en * x y * y serán iguales a 0 (ya que son iguales), lo que significa que la función establecerá tanto * x como * y establecido en 0.

Si tienen los mismos valores pero no la misma ubicación de memoria, todo funciona como se esperaba

*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

¿Debería usarse esto?

En casos generales, no. El compilador optimizará la variable temporal y dado que el intercambio es un procedimiento común, debería generar el código de máquina óptimo para su plataforma.

Tomemos como ejemplo este programa de prueba rápido escrito en 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;
}

Compilado usando:

gcc -Os main.c -o swap

La versión xor toma

real 0m2.068s
user 0m2.048s
sys 0m0.000s

Donde como la versión con la variable temporal toma:

real 0m0.543s
user 0m0.540s
sys 0m0.000s

Answer 15

Veamos un ejemplo c simple para intercambiar dos números sin usar la tercera variable.

programa 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();
}

Salida:

Antes del cambio a = 10 b = 20 Después del cambio a = 20 b = 10

Programa 2: Uso de * y /

Veamos otro ejemplo para intercambiar dos números usando * y /.

#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();
}

Salida:

Antes del cambio a = 10 b = 20 Después del cambio a = 20 b = 10

Programa 3: hacer uso del operador XOR bit a bit:

El operador XOR bit a bit se puede usar para intercambiar dos variables. El XOR de dos números xey devuelve un número que tiene todos los bits como 1 donde los bits de xey son diferentes. Por ejemplo, XOR de 10 (en Binario 1010) y 5 (en Binario 0101) es 1111 y XOR de 7 (0111) y 5 (0101) es (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;

Salida:

Después del intercambio: x = 5, y = 10

Programa 4:

Nadie ha sugerido usar std :: swap, aún.

std::swap(a, b);

No utilizo variables temporales y, dependiendo del tipo de ayb, la implementación puede tener una especialización que tampoco. La implementación debe escribirse sabiendo si un ''truco'' es apropiado o no.

Problemas con los métodos anteriores:

1) El enfoque basado en multiplicación y división no funciona si uno de los números es 0 ya que el producto se vuelve 0 independientemente del otro número.

2) Ambas soluciones aritméticas pueden causar desbordamiento aritmético. Si xey son demasiado grandes, la suma y la multiplicación pueden salir del rango entero.

3) Cuando usamos punteros a una variable y hacemos un intercambio de función, todos los métodos anteriores fallan cuando ambos punteros apuntan a la misma variable. Echemos un vistazo a lo que sucederá en este caso si ambos apuntan a la misma variable.

// Método basado en Bitwise XOR

x = x ^ x; // x becomes 0
x = x ^ x; // x remains 0
x = x ^ x; // x remains 0

// Método basado en aritmética

x = x + x; // x becomes 2x
x = x – x; // x becomes 0
x = x – x; // x remains 0

Veamos el siguiente programa.

#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;
}

Salida :

Después del intercambio (& x, & x): x = 0

El intercambio de una variable consigo mismo puede ser necesario en muchos algoritmos estándar. Por ejemplo, vea esta implementación de QuickSort donde podemos intercambiar una variable consigo mismo. El problema anterior se puede evitar poniendo una condición antes del intercambio.

#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;
}

Salida :

Después del intercambio (& x, & x): x = 10

Answer 16

ese es el algoritmo de intercambio XOR correcto

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;
}
}
}

debe asegurarse de que las ubicaciones de memoria sean diferentes y también que los valores reales sean diferentes porque A XOR A = 0

Answer 17

la forma general es:

A = A operation B
B = A inverse-operation B
A = A inverse-operation B

sin embargo, debe tener cuidado con los desbordamientos y tampoco todas las operaciones tienen un inverso que esté bien definido para todos los valores en los que se define la operación. ej. * y / work hasta que A o B sea 0

xor es particularmente agradable ya que se define para todos los ints y es su propia inversa

Answer 18

solución de una sola línea para intercambiar dos valores en lenguaje c.

a=(b=(a=a+b,a-b),a-b);

Answer 19

#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;
}

Actualización: en esto estamos tomando la entrada de dos enteros del usuario. Entonces estamos usando la operación XOR bit a bit para intercambiarlos.

Digamos que tenemos dos enteros a=4 b=9 y luego:

a=a^b --> 13=4^9
b=a^b --> 4=13^9
a=a^b --> 9=13^9

Answer 20

#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;
}

Answer 21

#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();
}

Answer 22

a = a + b
b = a - b // b = a
a = a - b

Answer 23

a = a + b - (b=a);

Es muy simple, pero puede provocar una advertencia.

Answer 24

public void swapnumber(int a,int b){
a = a+b-(b=a);
System.out.println("a = "+a +" b= "+b);
}

Answer 25

second_value -= first_value;
first_value += second_value;
second_value -= first_value;
second_value *= -1;