CS 3343/3341, Exclusive-Or

CS 3343/3341
Analysis of Algorithms

Exclusive-Or, XOR,⊕

Definition of Exclusive-or: Students sometimes are less familiar with xor than with other logical operators, but xor comes up very often, especially in cryptography. Here are definitions of and (∧), or (∨), and xor (⊕), based on truth tables:

a	b	a∧b	a∨b	a⊕b
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

Thus

a and b means "both a and b must be true".
a or b means "either a, or b, or both are true, but they are not both false".
a xor b means "either a or b are true, but not both, and they are not both false".

Properties of Exclusive-or:

Using Exclusive-or to Interchange Values:

Java, C, and C++ all support ^ as the bitwise exclusive-or operator. From the properties of xor, one can interchange the contents of two words using three statements without any extra storage:

// Xor.java: test xor function ^ for interchanges public class Xor { // main function to try out Base class public static void main (String[] args) { int a = 123456789, b = -987654321; printThem(a, b, 1); // interchange a and b int temp = a; a = b; b = temp; printThem(a, b, 2); a = 345678912; b = -765432198; printThem(a, b, 1); // interchange a and b a = a^b; b = a^b; a = a^b; printThem(a, b, 2); a = 234234234; b = -789789789; printThem(a, b, 1); // interchange a and b a ^= b; b ^= a; a ^= b; printThem(a, b, 2); } // end of main private static void printThem(int a, int b, int c) { if (c == 1) System.out.print("Before, "); else System.out.print("After, "); System.out.println("a: " + a + ", \tb: " + b); if (c != 1) System.out.println(); } } Here is the output of a run: % java Xor Before, a: 123456789, b: -987654321 After, a: -987654321, b: 123456789 Before, a: 345678912, b: -765432198 After, a: -765432198, b: 345678912 Before, a: 234234234, b: -789789789 After, a: -789789789, b: 234234234

// Xor.java: test xor function ^ for interchanges
public class Xor {
   // main function to try out Base class
   public static void main (String[] args) {
      int a = 123456789, b = -987654321;
      printThem(a, b, 1);
      // interchange a and b
      int temp = a;
      a = b;
      b = temp;
      printThem(a, b, 2);
      a = 345678912; b = -765432198;
      printThem(a, b, 1);
      // interchange a and b
      a = a^b;
      b = a^b;
      a = a^b;
      printThem(a, b, 2);
      a = 234234234; b = -789789789;
      printThem(a, b, 1);
      // interchange a and b
      a ^= b;
      b ^= a;
      a ^= b;
      printThem(a, b, 2);
   } // end of main

   private static void printThem(int a, int b, int c) {
      if (c == 1) System.out.print("Before, ");
      else        System.out.print("After,  ");
      System.out.println("a: " + a + ", \tb: " + b);
      if (c != 1) System.out.println();
   }
}
Here is the output of a run:
% java Xor
Before, a:  123456789,  b: -987654321
After,  a: -987654321,  b:  123456789

Before, a:  345678912,  b: -765432198
After,  a: -765432198,  b:  345678912

Before, a:  234234234,  b: -789789789
After,  a: -789789789,  b:  234234234

Revision date: 2012-05-27. (Please use ISO 8601, the International Standard Date and Time Notation.)