The XOR operator, short for Exclusive OR, is a fundamental concept in computer science, mathematics, and digital logic. Represented by the symbol ^ in many programming languages and ⊕ in mathematical notation, XOR is a logical operation that is widely used in various applications, including cryptography, data structures, and algorithms. This post will explore how the XOR operator works, its properties, and practical applications.

What is XOR?

The XOR operator compares two binary inputs and returns true (1) if the inputs are different, and false (0) if the inputs are the same. It can be summarized in a simple truth table:

The XOR operator is often referred to as an "exclusive OR" because it returns true exclusively when one input is true, but not both.

Key Properties of XOR

1. Identity Property:

   • XORing a value with 0 leaves the value unchanged:
     • A ⊕ 0 = A

2. Self-Inverse Property:

   • XORing a value with itself always results in 0:
     • A ⊕ A = 0

3. Commutativity:

   • The order of XOR operations does not matter:
     • A ⊕ B = B ⊕ A

4. Associativity:

   • XOR operations can be grouped in any order:
     • (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)

5. Cancelation:

   • XORing a value with another, then XORing again with the same value restores the original:
     • (A ⊕ B) ⊕ B = A

Applications of XOR

1. Finding the Unique Element

One of the most common applications of XOR in programming is finding the unique element in an array where every other element appears twice.

Example:

public int findUnique(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num; // XOR all elements
    }
    return result; // The unique number remains
}

This works because duplicate numbers cancel out, like: x ⊕ x = 0 .

2. Swapping Two Numbers Without a Temporary Variable

You can use XOR to swap two numbers without needing an extra variable:

Example:

int a = 5, b = 10;
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println("a: " + a + ", b: " + b); // Output: a: 10, b: 5

Here’s how it works step by step:

1. a = a ^ b → stores the XOR of a and b in a.
2. b = a ^ b → restores a to b by XORing again.
3. a = a ^ b → restores b to a by XORing again.

3. Bit Manipulation and Cryptography

The XOR operator is heavily used in cryptography for combining plaintext with a key to produce ciphertext. Since XOR is reversible (A ⊕ B) ⊕ B = A, it ensures secure encryption and decryption.

Example:

// Simple XOR Encryption
public String xorEncrypt(String message, char key) {
    char[] encrypted = new char[message.length()];
    for (int i = 0; i < message.length(); i++) {
        encrypted[i] = (char) (message.charAt(i) ^ key);
    }
    return new String(encrypted);
}

4. Find the Difference

In this problem on LeetCode.
You can use XOR to solve the problem.

Imagine, you have 2 strings like s = "abcd" and t = "abcde" and return the difference between then.

public char findTheDifference(String s, String t) {
        char result = 0;
        for (int i = 0; i < s.length(); i++) {
            result ^= s.charAt(i);
        }
        for (int i = 0; i < t.length(); i++) {
            result ^= t.charAt(i);
        }
        return result;
    }

Why Use XOR?

XOR is efficient, requiring minimal computational resources. It operates at the bit level, making it faster than many alternative methods for tasks like encryption, error detection, and more. Its unique properties make it a versatile tool for solving diverse problems in computing.

Summary

The XOR operator is a powerful and versatile tool in computing and mathematics. By understanding its properties and applications, you can leverage it to write efficient algorithms, solve complex problems, and even improve your understanding of low-level operations. Whether you’re optimizing algorithms or exploring cryptography, XOR is an indispensable part of your programming toolbox.

📍 Reference

• The XOR Operator in Java

👋 Talk to me

• LinkedIn
• Github
• Portfolio