XOR Basics

XOR Basics

XOR, or Exclusive OR, is one of the most useful operators in bit manipulation. It compares corresponding bits and produces 1 when the bits are different and 0 when they are the same.

XOR is represented using the caret symbol:

^

Its cancellation and reversibility properties make it useful for problems involving:

• Duplicate values

• Missing numbers

• Unique elements

• Bit toggling

• Range XOR queries

• Bitmask manipulation

• Parity checking

• Reversible transformations

Unlike addition, XOR does not create carries between neighbouring bit positions. Every pair of corresponding bits is processed independently.

What Is XOR?

XOR returns 1 only when exactly one of the two input bits is 1.

• 0 ^ 0 = 0

• 0 ^ 1 = 1

• 1 ^ 0 = 1

• 1 ^ 1 = 0

It can be understood as a difference detector:

• Equal bits produce 0.

• Different bits produce 1.

The word “exclusive” distinguishes XOR from regular OR:

• OR returns 1 when at least one input bit is 1, including when both are 1.

• XOR returns 1 only when the input bits are different.

XOR Truth Table

How Does XOR Work on Numbers?

When XOR is applied to two integers, their corresponding binary bits are compared.

Consider:

5 = 0101

3 = 0011

Compare every position:

Therefore:

0101 ^ 0011 = 0110

Since 0110 represents 6:

5 ^ 3 = 6

Why Is XOR Important?

XOR can combine values while allowing equal values to cancel each other.

Consider an array in which every element appears exactly twice except one:

[4, 1, 2, 1, 2]

XOR all elements:

4 ^ 1 ^ 2 ^ 1 ^ 2

Because XOR is commutative and associative, equal elements can be grouped:

4 ^ (1 ^ 1) ^ (2 ^ 2)

Using:

1 ^ 1 = 0

2 ^ 2 = 0

The expression becomes:

4 ^ 0 ^ 0 = 4

The duplicate values disappear, leaving the unique element.

This requires:

• O(N) time to process the array.

• O(1) auxiliary space because only one running XOR value is maintained.

The cancellation works because the duplicates appear an even number of times. XOR should not be applied blindly when the frequency pattern is different.

Core Properties of XOR

1. Identity Property

XORing a number with 0 leaves it unchanged:

A ^ 0 = A

For example:

7 ^ 0 = 7

At the bit level:

• 0 ^ 0 = 0

• 1 ^ 0 = 1

Every bit keeps its original value.

2. Self-Cancellation Property

XORing a number with itself produces 0:

A ^ A = 0

For example:

9 ^ 9 = 0

Every corresponding bit is equal, so every resulting bit becomes 0.

3. Commutative Property

The order of the operands does not affect the result:

A ^ B = B ^ A

For example:

5 ^ 3 = 3 ^ 5

This allows values in an XOR expression to be rearranged.

4. Associative Property

The grouping of XOR operations does not affect the result:

(A ^ B) ^ C = A ^ (B ^ C)

Because XOR is both commutative and associative, equal values can be brought together and cancelled.

5. Reversibility Property

Applying the same XOR value twice restores the original value:

(A ^ B) ^ B = A

Using self-cancellation:

A ^ (B ^ B)

= A ^ 0

= A

This property is useful for reversible transformations and XOR-based encoding.

6. Equality Property

If:

A ^ B = 0

then:

A = B

Every bit in A must match the corresponding bit in B for the XOR result to contain only zeros.

Important XOR Identities

Application 1: Find the Single Non-Duplicate Element

Given an array where every element appears exactly twice except one, find the element that appears once.

Consider:

arr = [6, 3, 5, 3, 5]

XOR all elements:

6 ^ 3 ^ 5 ^ 3 ^ 5

Rearrange equal values:

6 ^ (3 ^ 3) ^ (5 ^ 5)

Cancel the pairs:

6 ^ 0 ^ 0 = 6

Therefore, the single non-duplicate element is:

6

Algorithm

• Initialize a running XOR value with 0.

• Traverse every element of the array.

• XOR the current element with the running value.

• Allow equal elements to cancel through the XOR properties.

• Return the remaining value after the traversal.

Time Complexity: O(N) because every element is processed once.

Space Complexity: O(1) because only one running value is maintained.

Application 2: Find the Missing Number

Suppose an array contains N distinct values selected from the range 0 to N, with exactly one number missing.

Consider:

arr = [3, 0, 1]

The complete range should contain:

[0, 1, 2, 3]

XOR every expected number and every array element:

(0 ^ 1 ^ 2 ^ 3) ^ (3 ^ 0 ^ 1)

The common values cancel:

0 ^ 0 = 0

1 ^ 1 = 0

3 ^ 3 = 0

Only 2 remains.

Therefore, the missing number is:

2

Algorithm

• XOR all values from 0 to N.

• XOR the result with every element present in the array.

• Allow the values appearing in both groups to cancel.

• Return the remaining value as the missing number.

Time Complexity: O(N)

Space Complexity: O(1)

This method avoids the possible arithmetic overflow associated with calculating the sum from 0 to N.

Application 3: Toggle a Bit

XOR can toggle a selected bit using a mask.

To toggle bit i:

N ^ (1 << i)

If the selected bit is:

• 0, it becomes 1.

• 1, it becomes 0.

Consider:

N = 10 = 1010

Toggle bit 2:

1010 ^ 0100 = 1110

The updated value is:

14

Apply the same mask again:

1110 ^ 0100 = 1010

The original value is restored.

Application 4: Prefix XOR and Range XOR Queries

Prefix XOR applies the prefix-sum idea using XOR.

Create:

prefixXor[0] = 0

Each following position stores the XOR of all elements before it.

Consider:

arr = [5, 2, 7, 3]

The prefix XOR values are:

prefixXor = [0, 5, 7, 0, 3]

To find the XOR of the inclusive range [L, R], use:

Range XOR = prefixXor[R + 1] ^ prefixXor[L]

For:

L = 1, R = 3

Range XOR = prefixXor[4] ^ prefixXor[1]

= 3 ^ 5

= 6

The direct calculation gives:

2 ^ 7 ^ 3 = 6

This works because the prefix before L appears twice and cancels.

Complexity

Building the prefix XOR array takes:

O(N) time and O(N) space.

After preprocessing, each range-XOR query takes:

O(1) time.

Application 5: Find Two Non-Duplicate Elements

Suppose every element appears twice except two elements that appear once.

XORing all elements gives:

totalXor = firstUnique ^ secondUnique

Because the two unique values are different, totalXor contains at least one set bit. That bit represents a position where the two unique values differ.

The elements can then be divided into two groups:

• Elements with that bit set.

• Elements with that bit unset.

Duplicate values enter the same group and cancel. Each unique value enters a different group, allowing both answers to be recovered.

This is a common interview extension of the single non-duplicate problem.

XOR Swap

Two integer variables can mathematically be swapped using three XOR operations:

A = A ^ B

B = A ^ B

A = A ^ B

However, this method is generally not recommended in practical code because:

• It is less readable than using a temporary variable.

• Modern compilers already optimize normal swaps effectively.

• It can fail when both expressions refer to the same storage location.

• It does not provide a meaningful performance advantage in ordinary code.

XOR swap is useful for understanding XOR’s reversibility, but a normal swap should usually be preferred.

XOR-Based Reversible Masking

A value can be transformed using a key:

encoded = value ^ key

Applying the same key again restores the original value:

encoded ^ key = value

This demonstrates XOR’s reversibility, but a simple repeated XOR key should not be treated as secure encryption. If the key is predictable, reused, or shorter than the protected data, the result may be easy to analyse and recover.

Secure cryptographic systems require properly designed algorithms and key management.

XOR and Addition Are Not the Same

XOR resembles binary addition without carrying.

Consider:

5 = 0101

3 = 0011

XOR:

0101 ^ 0011 = 0110

The result is 6.

Normal addition:

5 + 3 = 8

The results differ because addition carries values between neighbouring bit positions, while XOR processes every bit independently.

XOR and addition produce the same result only when the two numbers have no common set bit:

A & B = 0

In that case, no carry is required.

XOR and OR Are Not the Same

For two input bits:

• OR returns 1 when at least one bit is 1.

• XOR returns 1 only when exactly one bit is 1.

The difference appears when both bits are set:

1 | 1 = 1

1 ^ 1 = 0

For example:

5 | 3 = 7

5 ^ 3 = 6

Operator Precedence

The precedence of XOR relative to comparison operators depends on the programming language.

In C++ and Java, equality operators such as == have higher precedence than bitwise XOR. Therefore, an expression such as:

A ^ B == 0

may not be grouped as intended.

Use explicit parentheses:

(A ^ B) == 0

Python groups this particular expression differently, but using parentheses keeps the intention clear and avoids relying on language-specific precedence rules.

XOR and Exponentiation

In programming, ^ commonly represents bitwise XOR. It should not automatically be interpreted as exponentiation.

For example:

2 ^ 3

does not generally mean 2³.

Languages provide their own exponentiation syntax or mathematical functions. For example, Python uses ** for exponentiation.

Always confirm the meaning of ^ in the language being used.

When Should XOR Be Considered?

Consider XOR when:

• Equal values need to cancel.

• Every duplicate appears an even number of times.

• One or two values appear differently from the remaining values.

• A selected bit must be toggled.

• A reversible bit transformation is required.

• Range XOR queries must be answered.

• A problem involves parity or bit differences.

• Extra memory used by a frequency structure should be avoided.

Before applying XOR, verify the exact frequency conditions. XOR preserves values appearing an odd number of times and cancels values appearing an even number of times.

Limitations of XOR

• XOR alone does not preserve element frequencies.

• It cannot identify every duplicate or count occurrences.

• A simple XOR result may combine several odd-frequency values.

• It does not recover the original operands from A ^ B unless additional information is available.

• It should not replace normal arithmetic operations without a valid reason.

• Repeated-key XOR is not secure encryption.

• Signed interpretation depends on the integer width and language.

Common Mistakes

• Confusing XOR with OR.

• Assuming XOR represents exponentiation.

• Applying the single-element trick without verifying that every other value appears exactly twice.

• Assuming values appearing three times will cancel completely.

• Forgetting to include the complete range from 0 to N in the missing-number problem.

• Using XOR when the actual frequency of every value is required.

• Ignoring language-specific operator precedence.

• Using XOR swap in production code without considering readability or aliasing.

• Treating simple XOR masking as secure encryption.

• Misinterpreting a signed XOR result without considering the fixed bit width.

FAQs

Q1. Which duplicate-frequency patterns can be handled directly using XOR?

Values appearing an even number of times cancel to 0, while values appearing an odd number of times remain in the combined XOR. The standard single-number method works when exactly one value appears an odd number of times and every other value appears an even number of times.

Q2. How can XOR find two values that appear once while every other value appears twice?

XORing all values produces the XOR of the two unique numbers. A set bit in that result identifies a position where the two numbers differ. Partitioning the array by that bit places the unique values into separate groups while duplicate pairs cancel within their groups.

Q3. Can XOR cause integer overflow?

XOR does not produce carry-based arithmetic overflow. Its result always fits within the same fixed bit width as its operands. However, setting the highest bit may cause the result to be interpreted as negative when a signed integer type is used.

Q4. Can XOR be used to answer range queries efficiently?

Yes. A prefix XOR array can be built in O(N) time. The XOR of any inclusive range [L, R] can then be calculated in O(1) using prefixXor[R + 1] ^ prefixXor[L].

Q5. Why is XOR swap generally avoided even though it uses no temporary variable?

It reduces readability, provides no reliable performance benefit over a normal swap, and may fail when both operands refer to the same storage location. Modern compilers handle ordinary swaps efficiently, so the clearer method is preferred.