1. Introduction

XOR stands for Exclusive OR. It is a bitwise operator used to compare two bits.

In Java, XOR is represented by the ^ operator.

XOR Truth Table

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

Key Properties:

1. a ^ 0 = a → XOR with 0 keeps the number unchanged
2. a ^ a = 0 → XOR of a number with itself is 0
3. a ^ b = b ^ a → XOR is commutative
4. (a ^ b) ^ c = a ^ (b ^ c) → XOR is associative

These properties make XOR extremely useful in bitwise operations and coding problems.

---

2. XOR in Java

Syntax:

int result = a ^ b;

• a and b are integers
• The operator ^ performs bitwise XOR

Example:

public class XORDemo {
    public static void main(String[] args) {
        int a = 5; // 0101 in binary
        int b = 3; // 0011 in binary

        int result = a ^ b; // 0101 ^ 0011 = 0110 = 6
        System.out.println(result); // Output: 6
    }
}

Explanation:

  0101 (5)
^ 0011 (3)
= 0110 (6)

---

3. Common XOR Patterns

XOR is widely used in algorithmic problems because of its unique properties.

Pattern 1: Find the single non-duplicate element

Problem: In an array where every element appears twice except one, find the unique element.

public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num; // XOR all numbers
    }
    return result;
}

Explanation:

• Pairs cancel out because a ^ a = 0
• XOR with 0 gives the unique element
• Time Complexity: O(n), Space Complexity: O(1)

---

Pattern 2: Swap two numbers without using a temporary variable

int a = 5;
int b = 9;

a = a ^ b; // a = 5 ^ 9
b = a ^ b; // b = (5^9) ^ 9 = 5
a = a ^ b; // a = (5^9) ^ 5 = 9

System.out.println(a + " " + b); // Output: 9 5

Explanation:
XOR can swap values without extra memory.

---

Pattern 3: Find two numbers that appear once

Problem: In an array, every number appears twice except two numbers. Find them.

Approach:

1. XOR all elements → result = x ^ y (two unique numbers)
2. Find a set bit in result → separates numbers into two groups
3. XOR elements in each group → get the two numbers

This is a classic advanced XOR trick used in coding interviews.

---

Pattern 4: Check if two numbers have opposite signs

int x = 10;
int y = -5;

if ((x ^ y) < 0) {
    System.out.println("Opposite signs");
} else {
    System.out.println("Same signs");
}

Explanation:

• XOR of numbers with opposite signs has most significant bit = 1 → negative number
• Same signs → XOR non-negative

---

Pattern 5: XOR for subsets and bitmask problems

• XOR is used in problems like subsets, subsets with XOR sum, Gray code, and parity problems.
• For example, to calculate XOR of all subsets efficiently, XOR properties can help cancel duplicates.

---

4. XOR vs OR & AND

Operator	Symbol	Behavior
AND	&	Bit is 1 if both bits are 1
OR	|	Bit is 1 if at least one bit is 1
XOR	^	Bit is 1 if exactly one bit is 1

Use XOR when you want to toggle bits or detect differences.

---

5. Advanced XOR Properties

1. Self-inverse property: a ^ b ^ b = a
2. Zero property: a ^ 0 = a
3. Cumulative XOR:
   • XOR of numbers 1 to n can be computed in O(1) using pattern: n % 4 == 0 → XOR = n n % 4 == 1 → XOR = 1 n % 4 == 2 → XOR = n + 1 n % 4 == 3 → XOR = 0

This is used in find missing number problems.

---

6. Practical Use-Cases

1. Find unique elements in arrays
2. Detect errors using parity bits
3. Efficient swapping of variables
4. Bit manipulation problems in competitive programming
5. Gray code generation and subset XOR problems
6. Fast computation of cumulative XOR / prefix XOR

---

7. Example: Find Missing Number Using XOR

Problem: Given array [0,1,3], find the missing number 2.

int[] nums = {0, 1, 3};
int n = nums.length; // 3
int xorAll = 0;

// XOR all numbers from 0 to n
for (int i = 0; i <= n; i++) xorAll ^= i;

// XOR all elements in array
for (int num : nums) xorAll ^= num;

System.out.println(xorAll); // Output: 2

Explanation:

• All numbers present twice in XOR cancel out
• Missing number remains

---

8. Key Takeaways

1. XOR is a bitwise operator: ^ in Java.
2. XOR properties:
   • a ^ a = 0, a ^ 0 = a, commutative, associative
3. XOR is widely used in array problems, swapping, parity checks, and bitmask manipulations.
4. Efficient for finding unique elements, missing numbers, and subsets with XOR calculations.
5. Often combined with bitwise AND/OR in competitive programming problems.