XOR - The Magic Swap
Written by Alex Armstrong   
Friday, 13 July 2018
Article Index
XOR - The Magic Swap
XOR Hashing

The XOR Hash

The XOR "trick" of seeming to be able to store two values in one variable can also be used in other situations.

Suppose you have two values A and B and you want to return A when you know B and B when you know A. Then the usual way of doing this is to store both values and return the one you don't know. 

A simpler solution is to store

D= A XOR B

now when you are presented with a value X which is either A or B you return

X XOR D

which is B if X is A and A if X is B.

The best known example of where this can be used is when you want to build a doubly linked list. in this case each node in the list has to hold two references - one to the left node and one to the right node. Usually you would use two variables to store the references. Now you can see that you only need one. 

Pointer= Left XOR Right

Now if you are moving along the linked list from the start to the end you always have the pointer to the Left element - its where you have just come from. So 

Next = Pointer XOR Left

gives you the next node to move to on the right. 

If you are moving along the linked list from end to start then you always have the pointer to the Right element as it is just the node you have just come from. So 

Next = Pointer XOR Right

How worth while this sort of implementation is debatable. It saves one unit of storage per node and many programming languages don't allow this sort of manipulation with a reference - it being too low level. 

It is another fun use of the basic properties of the magic XOR swap. 

Are there more - yes in cryptography but that really is another story.

cereal

Related Articles

 
 

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Banner


The McCulloch-Pitts Neuron

Nowadays the McCulloch-Pitts neuron tends to be overlooked in favour of simpler neuronal models, but it was, and still is, important. It proved that something that behaved like a biological neuron was [ ... ]



Prime Numbers And Primality Testing

Testing to see if a number is a prime or not is the basis of many encryption and security methods. It has long been assumed that there is no fast way, i.e no polynomial time method, to determine if a  [ ... ]


Other Articles

 

 

pythondata

 



 

Comments




or email your comment to: comments@i-programmer.info

 


<ASIN: 0071460519>

<ASIN:0748621679>



Last Updated ( Friday, 03 August 2018 )