AND Gate
Outputs true only when all inputs are true.
Outputs true when inputs differ (exclusive or).
The XOR (Exclusive OR) gate outputs 1 when its inputs differ — one is 0 and the other is 1. When both inputs are the same, it outputs 0. Unlike the inclusive OR gate, which outputs 1 when both inputs are 1, the XOR gate excludes that case, hence its name. XOR occupies a special place in both computer science theory and practical engineering because of its unique algebraic properties, which make it indispensable for arithmetic circuits, error detection, cryptography, and countless algorithmic tricks. The XOR function was studied by mathematicians long before electronic computers existed, appearing in the context of modular arithmetic and parity calculations.
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XOR answers the question "are the inputs different?" It is equivalent to (A AND NOT B) OR (NOT A AND B). In Boolean algebra, it is written as A ⊕ B. Another way to express XOR is as the sum modulo 2: A XOR B gives the same result as (A + B) mod 2. This connection to modular arithmetic is not a coincidence — it makes XOR the natural operation for binary addition without carry, which is exactly what a half-adder computes. XOR can also be understood as a controlled inverter: when one input is 0, the output equals the other input unchanged; when one input is 1, the output is the inverse of the other input. This "conditional flip" behavior is the foundation of many of its applications.
Building an XOR gate from basic gates requires more transistors than AND, OR, or NOT gates. A straightforward implementation using the expression (A AND NOT B) OR (NOT A AND B) needs two NOT gates, two AND gates, and one OR gate. In CMOS technology, clever transistor-level design reduces this to approximately eight to twelve transistors depending on the specific topology. The added complexity is justified by the unique functionality XOR provides. In the TTL family, the 7486 chip provided four two-input XOR gates in a 14-pin package.
XOR is the complement of XNOR: A XOR B = NOT(A XNOR B). Unlike AND and OR, XOR is not monotone — increasing an input from 0 to 1 can either increase or decrease the output depending on the other input. XOR cannot be expressed using only AND and OR gates without also using NOT, which distinguishes it from the monotone Boolean functions. Interestingly, XOR alone is not functionally complete; you cannot build a NOT gate from XOR gates alone because XOR preserves the constant 0 (0 XOR 0 = 0). However, XOR combined with AND is functionally complete over the set of all Boolean functions.
XOR is fundamental in computing. It forms the core of half-adders and full-adders, which perform binary addition in arithmetic logic units. Every addition instruction your processor executes relies on chains of XOR gates computing sum bits. In parity checking, XORing all bits of a data word produces a single parity bit that can detect single-bit errors during data transmission. The XOR swap algorithm (A ^= B; B ^= A; A ^= B) exchanges two variables without a temporary variable, a classic trick in low-level programming. In cryptography, XOR is the basis of the one-time pad, the only provably unbreakable cipher, and is used extensively in stream ciphers and block cipher modes of operation. Checksum algorithms including CRC (Cyclic Redundancy Check) use XOR in polynomial division over GF(2). In competitive programming, XOR solves problems like "find the single unique element in an array where every other element appears twice" in O(n) time and O(1) space, exploiting the self-inverse property. In graphics programming, XOR drawing mode allows shapes to be drawn and erased by drawing them twice, since XORing a pixel value twice restores the original.
The concept of exclusive disjunction has roots in propositional logic, but XOR gained practical prominence with the rise of digital computing. Claude Shannon recognized its importance in switching circuit theory. Today, XOR is so central to computing that most processor architectures include a dedicated XOR instruction, and hardware designers treat it as a primitive operation alongside AND, OR, and NOT.