1. Introduction

The Bitwise XOR coding pattern is a frequently used technique in algorithmic problems where bit manipulation provides efficient solutions.

• XOR is represented by ^ in Java and most programming languages.
• XOR stands for exclusive OR, which means the result of each bit is 1 if exactly one of the bits is 1, otherwise 0.

XOR Truth Table

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

---

2. Important Properties of XOR

1. Self-canceling property: a ^ a = 0
2. Identity with zero: a ^ 0 = a
3. Commutative: a ^ b = b ^ a
4. Associative: (a ^ b) ^ c = a ^ (b ^ c)
5. Swapping values: a = a ^ b; b = a ^ b; // now b = original a a = a ^ b; // now a = original b

These properties make XOR extremely useful in arrays, streams, and bit manipulation problems.

---

3. When to Use XOR Pattern

The XOR pattern is most effective when:

1. You need to find unique elements in an array where other elements appear in pairs.
2. You need to swap values without extra space.
3. You want to calculate missing numbers in sequences efficiently.
4. You are working with bit-level problems, like subsets, parity, or Gray code.
5. You need efficient O(1) retrieval or elimination of duplicate elements in pairs.

Problem indicators:

• “Find the element that appears once”
• “Find two numbers appearing once”
• “Find missing number in a range”
• “Check parity or signs”

---

4. Core XOR Patterns

Pattern 1: Find Single Non-Duplicate Element

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

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

Explanation:

• Pairs cancel: a ^ a = 0
• XOR with zero leaves the number: 0 ^ unique = unique
• Time Complexity: O(n), Space Complexity: O(1)

---

Pattern 2: Swap Two Numbers Without Temporary Variable

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

Explanation:
XOR lets you swap without extra memory.

---

Pattern 3: Find Two Unique Numbers

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

Approach:

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

Time Complexity: O(n), Space Complexity: O(1)

---

Pattern 4: Find Missing Number Using XOR

int[] nums = {0, 1, 3};
int n = nums.length;
int xorAll = 0;
for (int i = 0; i <= n; i++) xorAll ^= i;
for (int num : nums) xorAll ^= num;
System.out.println(xorAll); // Output: 2

Explanation:

• XOR all numbers in the range with array elements
• Numbers appearing twice cancel
• Missing number remains

---

Pattern 5: XOR for Subsets & Bitmasking

• XOR is widely used in problems involving subset XOR sums or Gray code generation.
• XOR properties help efficiently combine elements and avoid duplicates.

Example: XOR of all subsets of [1,2,3] can be computed systematically using XOR combination properties.

---

Pattern 6: Check Opposite Signs Using XOR

int x = 10, y = -5;
if ((x ^ y) < 0) {
    System.out.println("Opposite signs");
} else {
    System.out.println("Same signs");
}

Explanation:

• XOR of numbers with opposite signs results in a negative number (MSB = 1)
• Same signs → non-negative

---

5. Bitwise XOR in Java – Syntax Recap

int result = a ^ b; // bitwise XOR

• Works for all integer types: int, long, short, byte
• Supports binary bit-level manipulation

---

6. Advanced XOR Tricks

1. Cumulative XOR from 1 to n: n % 4 == 0 → XOR = n n % 4 == 1 → XOR = 1 n % 4 == 2 → XOR = n + 1 n % 4 == 3 → XOR = 0 Useful for finding missing numbers or fast XOR computations.
2. Toggle specific bit: num ^= (1 << k); // toggles k-th bit
3. Check if a number is power of two: if ((n & (n - 1)) == 0) // true → power of 2
4. Parity check: Count 1s using XOR in clever ways.

---

7. Key Takeaways

1. XOR is a bitwise operator (^) used for exclusive OR operations.
2. Properties of XOR:
   • a ^ a = 0
   • a ^ 0 = a
   • Commutative & associative
3. XOR is useful in:
   • Finding unique elements in arrays
   • Finding missing numbers
   • Swapping variables
   • Subset XOR problems
   • Bitmask and Gray code problems
4. Efficient O(n) time and O(1) space solutions are possible using XOR.