XOR

Read This.

XOR is like cheating on your girlfriend: if you are alone with her it is ok, if you are alone with the other chick is ok, if you with none or with both you are screwed.

Properties of XOR

Here are several useful properties of XOR. This applies to plain XOR and bitwise XOR.

  • x (+) 0 = xXORing with 0 gives you back the same number. Thus, 0 is the identity for XOR.
  • x (+) 1 = \xXORing with 1 gives you back the negation of the bit. Again, this comes from the truth table. For bitwise XOR, the property is slightly different: x ^ ~0 = ~x . That is, if you XOR with all 1’s, the result will be the bitwise negation of x.
  • x (+) x = 0XORing x with itself gives you 0. That’s because x is either 0 or 1, and 0 (+) 0 = 0 and
    1 (+) 1 = 0.
  • XOR is associative.That is: (x (+) y) (+) z = x (+) (y (+) z).You can verify this by using truth tables.
  • XOR is commutative.That is: x (+) y = y (+) x.You can verify this by using truth tables.

Various Views of XOR

You can think of XOR in many ways. Assume that p and q are Boolean variables. Also assume that p1, p2, …pn are Boolean variables. Let (+) be the XOR operator (this is a circle with a plus sign inside it). In this case, we assume that p and q are boolean values, instead of words, and we assume (+) is plain XOR, not bitwise XOR. Later on, we’ll use it as bitwise XOR.

  • p (+) q is true if exactly one of p and q is true. This is the conventional definition of XOR.
  • p1 (+) p2 (+) … (+) pn is true if the number of variables with the value true is odd (and is false if the number of variables with the value true is even). Notice this definition ignores the variables which are assigned to false.This may seem like an odd view of XOR. (No pun intended). However, if you believe that XOR is associative (which it is), it’s merely an extension of the first definition of XOR.This definition makes sense, if you read the next definition.
  • p1 (+) p2 (+) … (+) pn is the same as adding modulo 2. If pi is true, then treat it as a 1, otherwise treat it as a 0. Then, XOR operation is equivalent to:
         p1 (+) p2 (+) ... (+) pn == ( p1 + p2 + ... + pn ) % 2
    

    Thus, XOR applied to a bunch of Boolean variables is the same as summing up all the variables’ values (where true is 1 and false is 0), and dividing mod 2. Recall that dividing mod 2 is one way to determine if a number is even or odd. Since only the variables that have value 1 contribute to the sum (0 is the identity value in sums), this determines how many variables have value 1.

Parity Check

People often use XOR as a means of doing a parity check. A bitstring has even parity if the number of 1’s in the string is even. It has an odd parity if the number of 1’s is odd. If you XOR the bits together, you can tell whether a bitstring has even or odd parity.

This can often be used to verify data sent across a network, where there’s some probability a bit may be corrupted. For example, suppose you’re sending N bytes across the network from a source location to a destination location.

How can you determine whether the bytes were sent correctly? One way is to use a kind of checksum, which uses XOR. Each byte can be written as b7b6…b0. For each byte, XOR all the bits in position bi.

If N was 10, and you’re transmitting 10 bytes, then create an 11th byte where bi is the XOR of all 10 bytes ith bit. This 11th byte is called the checksum. This checksum is also sent across the network.

At the destination end, where the data is being received, you can then independently perform the checksum again, and see if the checksum you performed matches the checksum sent across. If so, then you have some confidence that no bytes were corrupted. If it’s not the same, then the network has corrupted some bytes, and you may need to retransmit the data.

Clearly the system could have errors. For example, if two bits were flipped, say, bit 3 of bytes 4 and 5, then the checksum would be the same if they hadn’t been flipped, but there would still be errors. Nevertheless, it catches some errors.

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s