{"id":1494,"date":"2019-03-09T15:30:23","date_gmt":"2019-03-09T23:30:23","guid":{"rendered":"http:\/\/wonghoi.humgar.com\/blog\/?p=1494"},"modified":"2019-03-09T20:13:51","modified_gmt":"2019-03-10T04:13:51","slug":"explain-xor-tricks-succinctly-with-two-properties","status":"publish","type":"post","link":"https:\/\/wonghoi.humgar.com\/blog\/2019\/03\/09\/explain-xor-tricks-succinctly-with-two-properties\/","title":{"rendered":"Explain XOR tricks succinctly with two properties"},"content":{"rendered":"

Most teaching materials on XOR starts from its straight definition then a bunch of recipes for exploiting XOR. It is not convenient to remember and not intuitive to come up with new tricks on our own. Instead, I’d like to describe XOR as two intuitive operations:<\/p>\n

    \n
  1. Change detector (The logic definition itself)<\/li>\n
  2. Toggling light switches (Flipping twice undoes it)<\/li>\n<\/ol>\n

    The second interpretation (toggling) is actually way more powerful and easy to remember than the first interpretation (definition).<\/p>\n

    \n

    With the toggling interpretation, you don’t have to think hard to come up with the four algebraic properties:<\/p>\n

      \n
    1. Associativity<\/em> and commutativity<\/em>: we only care about whether the individual light switches (bits) are flipped odd (flipped) or even (not-flipped) number of times at the end of the day. When it happens in what order does not matter.<\/li>\n
    2. Identity<\/em>: flipping NONE of the switches (a mask of all 0) leaves it alone<\/li>\n
    3. Inverse<\/em>: pick only the switches that are already turned on (using itself as mask) and flip them (xor) guarantees to turn everything off (0)<\/li>\n<\/ol>\n
      \n

      The XOR swap trick can be constructed by exploiting the fact that flipping the same switch twice (at any point) reverts it back to where it started:<\/p>\n\n\n\n\n\n\n\n
      <\/td>\n\"x\"<\/td>\n\"y\"<\/td>\n<\/td>\n<\/tr>\n
      Start<\/td>\n\"x_0\"<\/td>\n\"y_0\"<\/td>\n<\/td>\n<\/tr>\n
      Mix \"y_0\" with \"x_0\"<\/td>\n\"x_1 = x_0 \oplus y_0\"<\/td>\n<\/td>\nNo info is lost, still have \"y_0\" somewhere to undo if we wish.<\/td>\n<\/tr>\n
      The incumbent \"y_0\" is used to cancel the \"y_0\" inside \"x_1\" to recover \"x_0\"<\/td>\n<\/td>\n\"\begin{array}{rcl}<\/td>\nSince \"y_0\" is already saved (mixed with) \"x_1\", we don’t have to worry about losing it as long as we get to our main goal of putting \"x_0\" in \"y\", which will be used as a recovery key later.<\/td>\n<\/tr>\n
      Now use the \"x_0\" stored in \"y_2\" to unmix \"x_1\" to recover \"y_0\"<\/td>\n\"\begin{array}{rcl}<\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

      Note that this trick is obsolete for modern computer architecture because<\/p>\n