refernce

Properties of XOR

  1. Commutative: A ⊕ B = B ⊕ A
  2. Associative: A ⊕ ( B ⊕ C ) = ( A ⊕ B ) ⊕ C
  3. Identity element: A ⊕ 0 = A
  4. Self-inverse: A ⊕ A = 0
  5. Parity: for any n bits, A1 ⊕ A2 ⊕ … ⊕ An = 1 (iff the # of 1s is odd)

Uses of XOR

  1. Toggling
//toggles between two values x and y
for (int n=x; true; n^=(x^y))
  cout<<n;
  1. Swapping without temproary variable 
    void s(int& a, int& b){
  a = a^b;
  b = a^b;
  a = a^b;
}

  2. Assembly Language
    XOR’ing a register with itself is the fastest way for the compiler to zero the register

  3. Doubly Linked List
    we can store XOR’d value of the previous and next pointers
    codes

  4. Encryption

  5. Error Detection
    XOR all bits to get a single parity bit and append it to the end of the message. If the received parity bit is different from the calculated one, a single bit has been corrupted. However, this cannot detect if two bits are corrupted.

  6. RAID data protection
    Create an additional hard drive which contains the XOR value of all other n drives.
    If a failure occurs on one drive, we can restore it from the others. (If 2 drives fail simultaneously, it does not work)