Exclusive or

Exclusive or

Venn diagram of XOR

Exclusive or (often abbreviated as XOR) is a logical operation that outputs true or 1 only when the inputs differ from one another. It is a fundamental operation in Boolean algebra and is widely used in digital electronics, cryptography, and computer science.

Definition

The exclusive or operation is defined on two operands. It returns true if and only if exactly one of the operands is true. In other words, XOR is true if the inputs are different. The operation can be symbolically represented as:

\( A \oplus B = (A \land \neg B) \lor (\neg A \land B) \)

where \( \land \) denotes logical conjunction (AND), \( \lor \) denotes logical disjunction (OR), and \( \neg \) denotes logical negation (NOT).

Truth Table

The truth table for XOR is as follows:

Truth table for XOR

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

Properties

Venn diagram showing XOR

XOR has several important properties:

• Commutative: \( A \oplus B = B \oplus A \)
• Associative: \( (A \oplus B) \oplus C = A \oplus (B \oplus C) \)
• Identity element: \( A \oplus 0 = A \)
• Self-inverse: \( A \oplus A = 0 \)

These properties make XOR a useful operation in various computational and mathematical contexts.

Applications

Digital Electronics

In digital electronics, XOR gates are used to perform bitwise operations. They are fundamental components in arithmetic logic units (ALUs) and are used in error detection and correction algorithms, such as parity bit generation.

Cryptography

XOR in cryptography

XOR is a key operation in many cryptographic algorithms. It is used in stream ciphers and block ciphers to combine plaintext with a key stream, providing a simple yet effective method of encryption.

Computer Science

In computer science, XOR is used in various algorithms and data structures. It is employed in checksum calculations, hash functions, and pseudo-random number generators. XOR is also used in bit manipulation techniques to swap values without using a temporary variable.

Variadic XOR

Variadic XOR operation

The XOR operation can be extended to more than two operands, known as variadic XOR. The result is true if an odd number of the operands are true. This property is useful in error detection and coding theory.

Related pages

• Logical conjunction
• Logical disjunction
• Logical negation
• Boolean algebra
• Digital logic