Computer hardware architects need to use more logical operators than and & or in their work. One example is the exclusive-or operator, which can be defined in Python like this:

1
2
3
4
5
def Xor(A,B):
  if A==B:
     return False
  else:
     return True

One can see from this function, that it only returns True if one of the two arguments is different from the other. Now given, this simple function, the goal is to write an accumulation of Xor over all the items of a sequence.

Before launching into the design, it is helpful to consider a a case for a sequence, and become comfortable with how the answer is calculated. Suppose the sequence is [True,False,False,True]. Letting "@" be a symbol representing Xor, what we need to calculate is True @ False @ False @ True. That works out to be

Xor(Xor(Xor(True,False),False),True)

This is not so easy to see! Based on the way Python evaluates expressions, the first thing to do with the expression above is to calculate Xor(True,False) -- the first two items of the sequence. After doing that, Python should combine (using Xor) with the third item, and so on. If this is puzzling, it can help to think first about how summing works (like 1+2+3+4 and what would be an expression using a two-parameter Add function).

Now we resume the design, asking the question, what should be the accumulation variable? It should initially be something that works for an empty sequence or even a sequence with one item. Here is a clever idea: choose an initial value Accum so that Xor(Accum,S[0]) is S[0]. That way, if the sequence happens to have one item (namely, S[0]), then the result will be S[0]. Also, if the sequence has two items, the answer will be Xor(S[0],S[1]). So what is the initial value for such an Accum variable? If S[0] is True, Accum should be False; but if S[0] is False, Accum should be False. Turns out, by happy accident, that Accum can be False in any case.

1
2
3
4
5
def XorAccum(S):
  Accum = False 
  for item in S:
    Accum = Xor(Accum,item)
  return Accum

As a check on this design, suppose S is [True,False]. The loop will then have two iterations. The first iteration will assign Accum to be Xor(False,True), so Accum will be True. The second iteration will assign Accum = Xor(True,False), because item will be False in the second iteration. The result will then be False, which is correct. Of course, such a little test on the code is not convincing that it has no bugs, but we can try more such tests, in principle, to gain confidence.