The XOR Operator and Its Applications to Programming

Note#89

notes
Published

2023-05-24

Introduction to XOR Operator

In computer science, the XOR (exclusive or) operator is a fundamental binary operation that operates on two boolean inputs. It returns true (or 1) if the number of true inputs is odd and false (or 0) if the number of true inputs is even. Put simply, it gives you a true result if, and only if, just one of your inputs is true.

If we have two binary inputs A and B, the XOR operation is represented as A XOR B, and its truth table is as follows:

A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0

XOR Properties

The XOR operator possesses certain properties which can be harnessed for problem-solving in programming:

1) Commutative

A XOR B = B XOR A

The order of the operands does not affect the result. For instance, if A=1 and B=0, then A XOR B = 1 and B XOR A = 1.

2) Associative

(A XOR B) XOR C = A XOR (B XOR C)

Grouping of the operands does not affect the result. If A = 1, B = 0, and C = 1, then both (A XOR B) XOR C and A XOR (B XOR C) give 0.

3) Identity

A XOR 0 = A

XORing any number with 0 results in the original number. For instance, 1 XOR 0 = 1.

4) Self-Inverse

A XOR A = 0

XORing any number with itself gives 0. For instance, 1 XOR 1 = 0.

5) Inverse

A XOR B XOR B = A

If a number A is XORed with B twice, the original number A is returned.

For instance, if A = 5 (in binary 101) and B = 3 (in binary 011), then A XOR B XOR B results in (5 XOR 3) XOR 3 = 6 XOR 3 = 5, which gives us back A.

XOR in Programming Languages

In many popular programming languages, the XOR operation is represented using the ^ symbol.

  • Python: A ^ B
  • C++/Java: A ^ B
  • JavaScript: A ^ B

XOR Applications in Programming: Problem Solving

Problem 1: Find the Missing Number

We are given an array of n - 1 integers which are in the range between 1 and n. All numbers appear exactly once, except one number, which is missing. Our task is to find this missing number.

The problem can be solved by exploiting the XOR properties.

Algorithm

  1. Initialize two variables X1 and X2 to 0.
  2. Loop through all the numbers from 1 to n. For each number i, XOR it with X1. By the end of the loop, X1 will hold the XOR of all numbers from 1 to n.
  3. Loop through the array. For each element num, XOR it with X2. By the end of the loop, X2 will hold the XOR of all elements in the array.
  4. XOR X1 with X2. The result is the missing number.
def find_missing_number(arr, n):
    X1, X2 = 0, 0

    # XOR all the numbers from 1 to n
    for i in range(1, n+1):
        X1 = X1 ^ i

    # XOR all the elements in the array
    for num in arr:
        X2 = X2 ^ num

    # The missing number is X1 XOR X2
    return X1 ^ X2

Problem 2: Find the Unique Number

A more generalized problem where all elements in an array appear twice except one, and our task is to find that unique element.

This problem can be solved by using the property A XOR A = 0 and A XOR 0 = A.

Algorithm

  1. Initialize a variable unique as 0.
  2. Loop through the array and XOR each element with unique.
  3. By the end of the loop, unique will hold the unique number.
def find_unique_number(arr):
    unique = 0

    # XOR all the elements in the array
    for num in arr:
        unique = unique ^ num

    # The result will be the unique number
    return unique

Interesting (but Useless) Trick: Swapping Variables

The XOR swap trick is more of a neat parlor trick than anything else. In modern high-level languages and with today’s compiler optimizations, there’s generally no reason to use XOR swap instead of traditional swapping with a temporary variable (or with the pythonic a, b = b, a). However, it’s a good demonstration of how XOR works and how you can take advantage of its unique properties.

Conventionally, if we wanted to swap the values of two variables, we would need a temporary variable to hold the value of one variable during the operation. For example:

def swap(a, b):
    temp = a
    a = b
    b = temp
    return a, b

However, the XOR operator allows us to swap values without the need for a temporary variable.

Algorithm

  1. Let a and b be the two numbers to be swapped.
  2. Execute a = a XOR b.
  3. Execute b = a XOR b (since a is now a XOR b, this is equivalent to b = (a XOR b) XOR b, which simplifies to b = a according to the inverse property).
  4. Finally, execute a = a XOR b (at this stage b is already a, so this is equivalent to a = (a XOR b) XOR a, which simplifies to a = b).
def swap_without_temp(a, b):
    a = a ^ b
    b = a ^ b
    a = a ^ b
    return a, b