Abstract


  • Exclusive OR, not equal
  • Returns true only when 2 inputs aren’t the same

Self-Inverse

XOR summation

Given a list of Integer (整数) , let be the XOR summation of the list of integers , and then we put into the list. Shuffle the list randomly

Now when we pick the first element or a random element from the list, we are sure it is the XOR summation of the rest of the integers

Proof using Cases and Self-inverse, Own-Inverse and Commutativity (交换律). There are 2 possible outcomes of picking a random integer from the list

  1. , is the XOR summation by definition
  2. , is an integer that is in the given list
  • For to be the XOR Summation of the rest of the elements, it must fulfil the following
  • We can expand the at the RHS, and we get
  • We can re-arrange the RHS with commutativity, and we get
  • With Self-Inverse and Own-Inverse, we can reduce the RHS to
  • Since RHS is equal to LHS, is valid. Thus is the XOR summation of the rest of the elements

Practice problem: Codeforces - XOR Mixup

Own-Inverse

Chemistry with Self-Inverse

Given , we can get back by . Because based on Self-Inverse, and based on Own-Inverse

Swapping values without introducing a new variable
public class MyClass {
    public static void main(String args[]) {
      int x=10;
      int y=25;
      
      x = x ^ y; // x ^ x = y, x ^ y = x
      y = x ^ y; // x
      x = x ^ y; // y
 
      System.out.println("x: " + x);
      System.out.println("y: " + y);
    }
}

Logic Gate Implementation

The Mathematical Statement is

  1. OR: or must be true
  2. AND, NOT (De Morgan’s laws): Either or are false
  3. AND: The above 2 must be true in order to let the statement to be true