Error Detection and Correction:Small Applications of Exclusive-OrGreg PlaxtonTheory in Programming Practice, Spring 2005Department of Computer ScienceUniversity of Texas at AustinExclusive-Or (XOR, ⊕)• For Booleans p and q, p ⊕ q is true if exactly one of p and q is true,and false otherwise– When applied to bits, we treat 0 as false and 1 as true• Here are some basic properties of ⊕– Commutativity: x ⊕ y = y ⊕ x– Associativity: (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)– Zero and complementation: x ⊕ 0 = x, x ⊕ 1 = x– Inverse: x ⊕ x = 0, x ⊕ x = 1Theory in Programming Practice, Plaxton, Spring 2005Applying ⊕ to Words• Often we will be working with binary strings of a particular length,which we call words• Let x and y be two words• We interpret x ⊕ y as the binary string of length k with ith bit equalto the XOR of the ith bits of x and y, for all i• The value of the ith output bit only depends on the values of the ithinput bits– Because of this, many properties of ⊕ on words follow easily fromthe corresponding property of ⊕ on bits– Example: Associativity, commutativity of ⊕ on words• Similar comments apply to other binary operators such as ∧ and ∨Theory in Programming Practice, Plaxton, Spring 2005Applying ⊕ to Nonnegative Integers• Convert each operand to its binary representation• Pad the shorter operand with leading zeros• Compute the output word as on the previous slide• Convert the output word to the corresponding nonnegative integer• Similar comments apply to other binary operators such as ∧ and ∨Theory in Programming Practice, Plaxton, Spring 2005Outline• Small applications of ⊕:– Bit selection; toggling; exchange; storage for doubly-linked lists;Hamming distance• See the course packet for a detailed discussion of each of theseapplications• Here we will sketch alternate proofs based on the following two-stepapproach:– First, we give a proof for the special case of words of length 1 (i.e.,bits)– Then, we argue that the proof for the general case (i.e., words ofarbitrary length) followsTheory in Programming Practice, Plaxton, Spring 2005Selecting a Bit• Suppose we are given three Booleans (bits) x, y, and u• We’d like to compute a Boolean w that is equal to x if u is false andto y if u is true• We can set w to ((x ⊕ y) ∧ u) ⊕ x)Theory in Programming Practice, Plaxton, Spring 2005Forming a Word by Selecting Bits from Two GivenWords• Suppose we are given three words x, y, and u• We’d like to compute the word w with ith bit equal to that of x if theith bit of u is 0, and to that of y if the ith bit of u is 1, for all i• Since ⊕ and ∧ are bitwise operators, we can set w to ((x ⊕ y) ∧ u) ⊕ x)as on the previous slideTheory in Programming Practice, Plaxton, Spring 2005Toggling a Boolean Variable• We’d like to write a single assignment statement S that “toggles” thevalue of a Boolean variable x between two given Boolean values p andq– If x = p then S should set x to q– If x = q then S should set x to p• Solution: Initialize an auxiliary variable t to p ⊕ q and define S asx := x ⊕ tTheory in Programming Practice, Plaxton, Spring 2005Word Toggling• We’d like to write a single assignment statement S that “toggles” thevalue of a word x between two given words p and q– If x = p then S should set x to q– If x = q then S should set x to p• Since ⊕ is a bitwise operator, we can solve the problem as on theprevious slideTheory in Programming Practice, Plaxton, Spring 2005Exchanging the Values of Two Boolean Variables• We’d like to swap the values of two Boolean variables x and y withoutusing a temporary variable• Solution: Set x to x ⊕ y, then y to x ⊕ y, and then x to x ⊕ yTheory in Programming Practice, Plaxton, Spring 2005Exchanging the Values of Two Words• We’d like to swap the values of two words x and y without using atemporary variable• Since ⊕ is a bitwise operator, we can solve the problem as on theprevious slideTheory in Programming Practice, Plaxton, Spring 2005Storage for Doubly-Linked Lists• Normally each node of a doubly-linked list has two pointers, a “left”pointer and a “right” pointer• Can we get by with just one?• The trick: Just keep the XOR of the left and right pointers– Works if you always arrive at a node from either the left or rightneighbor (or via the head or tail pointer)– Won’t work if your application involves other pointers “outside” thelist data structure that point to nodes in the list• But remember Dijkstra’s advice: Avoid clever tricks like the plague!Theory in Programming Practice, Plaxton, Spring 2005Hamming Distance• The Hamming distance between two words x and y is the number of1s in x ⊕ y– Equal to the number of “bit flips” needed to transform x into y (orvice versa)• Claim: For any nonnegative integer k, Hamming distance defines a“metric space” over the set of all words of length k• Before attempting to prove this claim, we’ll need to look at thedefinition of a metric spaceTheory in Programming Practice, Plaxton, Spring 2005Metric Space• A distance function over a set S is a function from S × S to the reals• A distance function d defined on a set S is metric if it satisfies thefollowing properties for all x, y, and z in S– Nonnegativity: d(x, y) ≥ 0– Distinctness: d(x, y) = 0 iff x = y– Symmetry: d(x, y) = d(y, x)– Triangle inequality: d(x, y) + d(y, z) ≥ d(x, z)• A metric space is a set with an associated metric distance function• Numerous applications give rise to computational problems defined overmetric spaces– Example: Automatic clustering of web pagesTheory in Programming Practice, Plaxton, Spring 2005An Observation Concerning Metric Spaces• Suppose that (S, d) is a metric space• Let k be a nonnegative integer and letd0(x, y) =X1≤i≤kd(xi, yi)for all x = (x1, . . . , xk) and y = (y1, . . . , yk) in Sk• Observation (not hard to prove; try it!): (Sk, d0) is a metric space• How can we use this observation to prove that Hamming distancedefines a metric space over the set of all words of a given length?Theory in Programming Practice, Plaxton, Spring 2005Hamming Distance Defines a Metric Space• Claim: For any nonnegative integer k, Hamming distance defines ametric space over the set of all words of length k• By the lemma stated on the previous slide, the claim follows if we canestablish that Hamming