Articoli Manifesto Tools Links Canali Libri Contatti ?
Programmazione

Lo XOR

Abstract
Tra gli operatori booleani normalmente conosciuti viene a volte tralasciato lo XOR. Questo operatore ben conosciuto da chi si occupa di sicurezza, è un elemento molto più interessante di quel che si può pensare. Proviamo a curiosarci un pò.
Data di stesura: 12/10/2007
Data di pubblicazione: 18/10/2007
Ultima modifica: 18/10/2007
di Stefano Fago Discuti sul forum   Stampa

XOR, operatore booleano

La tabella di verità dello XOR o OR Esclusivo, è nella forma:

T T F
T F T
F T T
F F F

in generale, quindi, quando i due operandi sono uguali si ottiene un FALSE altrimenti un TRUE.

È possibile esprimere lo XOR in funzione degli altri operatori più conosciuti nella forma: 

(a OR b) AND (NOT(a AND b))

Usi (quasi) pratici dello XOR

È possibile usare questo operatore in diverse situazioni pratiche anche se spesso è possibile farne a meno, preferendo forme più esplicite e meno efficienti a favore della legibilità.

L'operatore XOR viene può essere usato nelle tecniche di bit masking per attuare il flip di un bit

Ad esempio, supponiamo di avere l'espressione,in pseudo codice: 

if ( condition ){
  toggle = NOT toggle;
}

È possibile scrivere la stessa cosa nella forma:

toggle = toggle XOR condition;

Un'altro statement analogo, dati tre element a, b e x, è il seguente: 

if(x==a) x=b
else x=a

e può essere tradotto nella formula:

x = a XOR b XOR x

Infatti sostituendo all'elemento x, l'elemento a si ottiene x= a xor a xor b = b; avendo x=b si otterrebbe x = b xor b xor a = a.

Uno uso, in passato, più conosciuto è quello dello Swap tra interi, per cui è possibile attuare lo scambio di due valori numerici senza usare una variabile di appoggio; normalmente infatti avremmo: 

opA = 5
opB = 3

tmp = opA
opA = opB
opB = tmp

utilizzando lo XOR, risulterà: 

opA = opA xor opB
opB = opA xor opB
opA = opA xor opB

Possiamo vedere la differenza tra i due approcci con del codice d'esempio 

  1. class IntHolder { 
  2.   public int value; 
  3.  
  4.   public IntHolder() { 
  5.     this(0); 
  6.   } 
  7.  
  8.   public IntHolder(int value) { 
  9.     this.value = value; 
  10.   } 
  11.  
  12.   public String toString() { 
  13.     return String.valueOf(value); 
  14.   } 
  15. } 
  16.  
  17. // ... 
  18.  
  19. public static void normalSwap(IntHolder a, IntHolder b) { 
  20.   int valA = a.value; 
  21.   int valB = b.value; 
  22.   int swap = valA; 
  23.  
  24.   valA = valB; 
  25.   valB = swap; 
  26.  
  27.   a.value = valA; 
  28.   b.value = valB; 
  29. } 
  30.  
  31. public static void xorSwap(IntHolder a, IntHolder b) { 
  32.   int valA = a.value; 
  33.   int valB = b.value; 
  34.  
  35.   valA = valA ^ valB; 
  36.   valB = valA ^ valB; 
  37.   valA = valA ^ valB; 
  38.   a.value = valA; 
  39.   b.value = valB; 
  40. } 

XOR e strutture dati

Nell'ambito delle strutture dati è da citarsi la XOR Linked-List. Questa è una particolare variante della Double Linked-List, sviluppata per diminuire lo spazio occupato in memoria, sfruttando l'aritmetica dei puntatori e lo XOR: è possibile infatti memorizzare l'indirizzo dell'elemento precedente e dell'elemento successivo in un unico campo a differenza del normale approccio in cui sono necessari due puntatori. I difetti di questa struttura dati sono molteplici e di fatto la rendono utilizzabile in ambiti ridotti.

In Java è possibile simulare questa struttura ricreando i puntatori con la classe sun.misc.Unsafe come nel codice che segue: 

  1. import sun.misc.Unsafe; 
  2. import java.lang.reflect.*; 
  3.  
  4. public class PointerUtils { 
  5.   // 
  6.   private static Unsafe unsafe; 
  7.  
  8.   // 
  9.   private static int fieldOffset; 
  10.  
  11.   // 
  12.   private static PointerUtils instance = new PointerUtils(); 
  13.  
  14.   static { 
  15.     try { 
  16.       Class objectStreamClass = Class.forName("java.io.ObjectStreamClass$FieldReflector"); 
  17.       Field unsafeField = objectStreamClass.getDeclaredField("unsafe"); 
  18.  
  19.       unsafeField.setAccessible(true); 
  20.       unsafe = (Unsafe) unsafeField.get(null); 
  21.       fieldOffset = unsafe.fieldOffset(PointerUtils.class.getDeclaredField("obj")); 
  22.     } catch (Exception ex) { 
  23.       throw new RuntimeException(ex); 
  24.     } 
  25.   }; 
  26.  
  27.  
  28.   // 
  29.   private Object obj; 
  30.  
  31.  
  32.   public synchronized static long toAddress(Object o) { 
  33.     instance.obj = o; 
  34.  
  35.     return unsafe.getLong(instance, fieldOffset); 
  36.   } 
  37.  
  38.   public synchronized static Object toObject(long address) { 
  39.     unsafe.putLong(instance, fieldOffset, address); 
  40.  
  41.     return instance.obj; 
  42.   } 
  43. }// END 

Un Java XORLinkedList può essere la seguente: 

  1. import java.util.*; 
  2.  
  3. public class XORLinkedList { 
  4.   // 
  5.   private LLEntry head, tail; 
  6.  
  7.   // 
  8.   private int size = 0; 
  9.  
  10.  
  11.   public Iterator iterateForward() { 
  12.     return new LLIterator(head); 
  13.   } 
  14.  
  15.   public Iterator iterateReverse() { 
  16.     return new LLIterator(tail); 
  17.   } 
  18.  
  19.   public void addAtTail(Object o) { 
  20.     if (tail == null) { 
  21.       head = tail = new LLEntry(o, 0); 
  22.     } else { 
  23.       LLEntry e = new LLEntry(o, PointerUtils.toAddress(tail)); 
  24.       tail.pointers = tail.pointers ^ PointerUtils.toAddress(e); 
  25.       tail = e; 
  26.     } 
  27.   } 
  28.  
  29.   public void addAtHead(Object o) { 
  30.     if (head == null) { 
  31.       head = tail = new LLEntry(o, 0); 
  32.     } else { 
  33.       LLEntry e = new LLEntry(o, PointerUtils.toAddress(head)); 
  34.       head.pointers = head.pointers ^ PointerUtils.toAddress(e); 
  35.       head = e; 
  36.     } 
  37.   } 
  38.  
  39.   public static class LLEntry { 
  40.     public Object data; 
  41.     public long pointers; 
  42.  
  43.     public LLEntry(Object data, long pointers) { 
  44.       this.data = data; 
  45.       this.pointers = pointers; 
  46.     } 
  47.   } 
  48.  
  49.   public static class LLIterator implements Iterator { 
  50.     private long lastPtr; 
  51.     private LLEntry currentEntry; 
  52.  
  53.     public LLIterator(LLEntry head) { 
  54.       lastPtr = 0; 
  55.       currentEntry = head; 
  56.     } 
  57.  
  58.     public boolean hasNext() { 
  59.       return currentEntry != null; 
  60.     } 
  61.  
  62.     public Object next() { 
  63.       long nextPtr = currentEntry.pointers ^ lastPtr; 
  64.       lastPtr = PointerUtils.toAddress(currentEntry); 
  65.       Object data = currentEntry.data; 
  66.  
  67.       if (nextPtr == 0) { 
  68.         currentEntry = null; 
  69.       } else { 
  70.         currentEntry = (LLEntry) PointerUtils.toObject(nextPtr); 
  71.       } 
  72.  
  73.       return data; 
  74.     } 
  75.  
  76.     public void remove() { 
  77.       throw new UnsupportedOperationException(); 
  78.     } 
  79.   } 
  80.  
  81.  
  82.   public static void main(String[] args) { 
  83.     XORLinkedList l = new XORLinkedList(); 
  84.  
  85.     l.addAtTail("a"); 
  86.     l.addAtTail("b"); 
  87.     l.addAtTail("c"); 
  88.     l.addAtTail("d"); 
  89.  
  90.     System.err.println("forward..."); 
  91.  
  92.     for (Iterator i = l.iterateForward(); i.hasNext();) { 
  93.       System.err.println("got: " + i.next()); 
  94.     } 
  95.  
  96.     System.err.println("reverse..."); 
  97.  
  98.     for (Iterator i = l.iterateReverse(); i.hasNext();) { 
  99.       System.err.println("got: " + i.next()); 
  100.     } 
  101.   } 
  102. }//END 

XOR ed encryption

Lo XOR può essere utilizzato per un semplice meccanismo di encryption, supponendo di avere una chiave formata da elementi effettivamente casuali. Se data[] è un array di byte di lunghezza N e supponiamo di avere una chiave formata da un array key[] della stessa lunghezza e del tutto casuale nella composizione, possiamo utilizzare l'algoritmo che segue: 

byte[] e = new byte[data.length];
  
for ( int idx=0; idx<data.length; idx++ ){
  e[idx] = (byte)( a[idx] ^ k[idx] );
}

È ora possibile ottenere i dati originali applicando sempre lo XOR a quanto trasmesso; è evidente la necessità dello scambio della chiave grazie alla quale sarà possibile attuare il procedimento inverso a quello ora esposto. L'algoritmo è nella forma: 

byte[] data = new byte[e.length];

for ( int idx=0; idx<e.length; idx++ ){
  data[idx] = (byte)( e[idx] ^ k[idx] );
}

Un soluzione di questo tipo non è adottabile in contesti reali, anche se l'operatore XOR è pesantemente usato in molti algoritmi di crypting tra cui DES.

XOR e numeri casuali

Un utilizzo interessante e con un buon riscontro pratico di questo operatore booleano è nella generazione di numeri casuali. Si deve ad un ricercatore, George Marsaglia, dell'università dello stato della Florida la formulazione di generatori di numeri casuali basati su operazioni binarie e precisamento utilizzando XOR e SHIFT. La velocità di generazione e la sufficiente resistenza alle collisioni di valori rende questa tecnica particolarmente efficace e discapito di tecniche che richiedono molta più memoria e potenza di calcolo. Un esempio di questa tecnica può essere il seguente, partendo da un seed dato dall'attuale time si sistema: 

  1. public class XorShift { 
  2.   private static int base = (int) System.currentTimeMillis(); 
  3.   private int x = 0; 
  4.  
  5.   public XorShift() { 
  6.     x =((int) System.currentTimeMillis() + base); 
  7.   } 
  8.  
  9.   public int next() { 
  10.     x ^= x << 6; 
  11.     x ^= x >>> 21; 
  12.     x ^= (x << 7); 
  13.  
  14.     return x; 
  15.   } 
  16. } 

Come si vede la routine di generazione sfrutta operazioni di shift oltre allo XOR e quindi sfrutta operazioni proprie dei più comuni processori. Si pensi che sulla generazione di 100000000(cento milioni) di numeri non si verifica alcuna collisione, esplicitando una buona casualità.

Informazioni sull'autore

Stefano Fago, classe 1973. Diplomato in ragioneria, ha conseguito il Diploma di Laurea in Informatica con un progetto legato alle interfacce grafiche soft-realtime in Java. Dopo esperienze in Alcatel ed Elea, ha svolto attività di consulenza come Software Developer e Trainer alla ObjectWay S.p.A. sede di Milano. Attualmente Software Designer presso la sezione Innovazione e Attività Progettuali di BPU Banca. Appassionato del linguaggio Java e di tutte le tecnolgie Object Oriented. Polistrumentista dilettante.

È possibile consultare l'elenco degli articoli scritti da Stefano Fago.

Altri articoli sul tema Programmazione.

Discuti sul forum   Stampa

Cosa ne pensi di questo articolo?

Discussioni

Questo articolo o l'argomento ti ha interessato? Parliamone.