En la programación de computadora, el intercambio XOR es un algoritmo que utiliza la operación XOR Bitwise a los valores distintos del intercambio de las variables que tienen el mismo tipo de datos sin usar una variable temporal.
El algoritmo
Los algoritmos de intercambio del estándar requieren el uso de una variable del almacenamiento temporal. Usar el algoritmo del intercambio de XOR, sin embargo, no hay almacenamiento temporal necesario. El algoritmo es como sigue: X: = X XOR Y Y: = X XOR Y X: = X XOR Y El algoritmo corresponde típicamente a tres instrucciones del código automático . Por ejemplo, en código del montaje de Sistema/370 de IBM: XR R1, R2 XR R2, R1 XR R1, R2 donde están R1 y R2 los registros y cada operación de XR deja su resultado en el registro nombrado en la primera discusión.Sin embargo, el problema todavía sigue siendo que si el x y el y utilizan la misma localización de almacenaje, el valor almacenado en esa localización será puesto a cero hacia fuera por la primera instrucción de XOR, y después sigue siendo cero; no será " intercambiado con el itself".
Impermeabilizar que el intercambio de XOR trabaja
La operación binaria XOR sobre cadenas binarias tiene las características siguientes (donde el denota XOR):L1. Commutativity :
L2. Associativity :
L3. la identidad de existe : hay un tales que para cualquier
L4. Cada elemento de tiene un inverso: ¡para cada , hay un tales que L4a. de hecho, cada elemento es su propio lo contrario: .
Las primeras cuatro características son la definición de un grupo abeliano . El último es una característica estructural del XOR compartido no no necesario por otros grupos abelianos o grupos en general.
Suponer que tenemos dos registros R1 y R2, como en la tabla abajo, con el A de los valores iniciales y el B respectivamente. Realizamos las operaciones abajo en orden, y reducimos nuestros resultados usar la lista de la característica arriba.
Cifrar el ejemplo
Una función C que ejecuta el algoritmo del intercambio de XOR: lang=" del ¡El cuerpo de esta función a veces se considera acortado al if (x! = y) *x^=*y^=*x^=*y; . Sin embargo, ésta es C inválida, debido a una carencia de la secuencia señala
Razones del uso en la práctica
El algoritmo no es infrecuente en código encajado de la asamblea, donde hay a menudo espacio muy limitado disponible para una variable temporal del intercambio, y esta forma de intercambio puede también evitar una carga/un almacén que puedan ser mucho más rápidos que la operación equivalente usar una variable temporal. En algunas arquitecturas, ciertas operaciones requieren sus operandos ser particularmente registros, requiriendo un intercambio; y todo el " disponible; temporary" los registros pueden ser funcionando almacenando otros datos. Algunos recopiladores de optimización que puede generar código usar XOR intercambian adentro estas situaciones.
Razones de la evitación en la práctica
En las CPU (de escritorio) modernas, la técnica de XOR es considerablemente más lenta que usar una variable temporal para hacer el intercambio. Una razón es que las CPU modernas se esfuerzan ejecutar comandos paralelamente; ver la tubería de la instrucción. En la técnica de XOR, las entradas a cada operación dependen de los resultados de la operación anterior, así que deben ser ejecutadas en orden terminantemente secuencial. Si la eficacia es de enorme interés, se aconseja para probar las velocidades de la técnica de XOR y de la variable temporal que intercambian en la arquitectura de blanco.
La instrucción de XCHG
Trabajo moderno de los recopiladores de optimización traduciendo el código se dan en una representación fluir-basada interna que transformen en gran medida antes de producir su salida del máquina-código. Estos recopiladores son más probables reconocer y optimizar un intercambio (temporal-basado) convencional que reconocer las declaraciones del idioma de alto nivel que corresponden a un intercambio de XOR. Muchas veces, se escribe qué mientras que un intercambio en código de alto nivel es traducido por el recopilador a una nota interna simple que dos variables han intercambiado direcciones de memoria, algo que cualquier cantidad de código automático. Otras veces, cuando la arquitectura de blanco lo apoya, el recopilador puede utilizar una sola instrucción de XCHG (intercambio) que realice el intercambio en una sola operación.Una operación de XCHG estaba disponible tan hace tiempo como 1964, en el PDP-6 (donde fue llamado intercambio) y en 1970 en el Datacraft 6024 series (donde fue llamado XCHG). El Intel 8086, lanzados en 1978, también incluyó una instrucción nombrada XCHG. Los tres de estas instrucciones intercambiadas se coloca con los registros, o los registros con memoria, pero no podían intercambiar el contenido de dos posiciones de memoria. El Motorola operación de s EXG de 68000 'puede intercambiar solamente los registros con los registros. El PDP-10 heredó la instrucción del intercambio de PDP-6, pero el PDP-11 (la máquina en el cual el lenguaje de programación C fue desarrollado) no hizo.
Sin embargo, la instrucción de XCHG en los procesadores modernos (e. x86 ) se debe utilizar solamente para intercambiar los registros y no la memoria, pues una instrucción implícita de la CERRADURA del se puede imponer por el procesador ante las posiciones de memoria implicadas de modo que la operación sea el atómico.
Alias
El intercambio de XOR también es complicado en la práctica por el alias . Según lo observado arriba, si se hace una tentativa XOR-intercambiar el contenido de una cierta localización consigo mismo, el resultado es que la localización está puesta a cero hacia fuera y su valor perdido. Por lo tanto, el intercambio de XOR no se debe utilizar oculto en un idioma de alto nivel si el alias es posible.Si la lengua permite, los detalles feos del intercambio se deben ocultar dentro de una macro o de una función en línea . No sólo hará el clarificante del código, pero también será posible cambiar a una diversa rutina de intercambio en caso de necesidad.
Variaciones
El principio subyacente del algoritmo del intercambio de XOR se puede aplicar a cualquier operación binaria reversible. El reemplazo de XOR por la adición y la substracción da un levemente diferente, pero en gran parte el equivalente, formulación: procedimiento AddSwap ( var X, Y del : número entero); el comienza si el del <> Y de X entonces comienza X: = X + Y; Y: = X - Y; X: = X - Y extremo extremo Desemejante del intercambio de XOR, esta variación requiere que el procesador subyacente o el lenguaje de programación utilice un método tal como aritmética modular o Bignums para garantizar que el cómputo delX + de Y no puede causar un error debido al desbordamiento del número entero. Por lo tanto, se ve más raramente en la práctica que el intercambio de XOR.
Ver también
Diferencia simétricaLista encadenada XOR
.
| Random links: | Comité especial de Naciones Unidas sobre Palestina | Kim Malthe-Bruun | Necrosis avascular | Arturo Bisguier | Astur |