# multiple xor (sum of parities)

If we have:

$b_1 \oplus b_2 = b_1 (1 - b_2) + b_2 (1 - b_1)$

what is (or are, if there are different versions) the compact general formula for a multiple "summation":

$b_1 \oplus b_2 \oplus \dotsb \oplus b_n$

[PS. Possibly in terms of ordinary addition/multiplications, avoiding modulus]

• I’m assuming that this is non-carrying addition of binary numbers or, equivalently, XOR of bit strings. Danikar’s given a compact notation, and I don’t know of any nicer description than to say that the $k$-th bit of the sum is $1$ iff the number of summands with the $k$-th bit equal to $1$ is odd. – Brian M. Scott Jan 8 '13 at 19:40
• Yes Brian, you can picture a sum numbers where the numbers are replaced with their parity (even numbers with $0$s and odd numbers with $1$s). I am interested in a general expression for the resulting parity. – Pam Jan 8 '13 at 19:43
• $(\sum_k b_k) \mod 2$. – copper.hat Jan 8 '13 at 19:43
• I don’t know of anything simpler than what I wrote in words and @copper.hat has just given symbolically. – Brian M. Scott Jan 8 '13 at 19:44
• Purely as an aside, it was surprising to me to discover that XORs are slightly problematic elements in the context of formally verifying correctness of digital hardware. – copper.hat Jan 8 '13 at 19:50

I think this will work:-

$$b_1 \oplus b_2 \oplus \cdots \oplus b_n = \frac{1 - \prod_{i=1}^n (1 - 2b_i)} 2$$

• Very neat. Looks like an "indicator" function for the number of $b$'s to be odd. – Pam Jan 8 '13 at 21:02

You can think of the sum as an OR, the multiplications as AND and $1-x$ as NOT $x$, that is you can read: $b_1 (1 - b_2) + (1 - b_1) b_2$ as "($b_1$ AND NOT $b_2$) OR (NOT $b_1$ AND $b_2$)".

For any fixed $n$, you can write a similar logical statement for $b_1 \oplus b_2 \oplus \cdots \oplus b_n$ and convert it back into a formula, but it will get messy quickly. For example, when $n=3$ it is: $b_1 b_2 b_3 + b_1 (1 - b_2) (1 - b_3) + (1 - b_1) b_2 (1 - b_3) + (1 - b_1) (1 - b_2) b_3$.

If you want you can write this as $$b_1 \oplus b_2 \oplus \cdots \oplus b_n = \sum_{(x_1, \ldots, x_n) \in X} \prod_{i=1}^n b_i x_i + (1 - b_i) (1 - x_i)$$ where `$X = \{ (x_1, \ldots, x_n) \in \{0, 1\}^n : \sum x_i \textrm{ is odd} \}$.

• Thank you qwerty1793. This seems definitely closer to what i was looking for (although i am still trying to "digest" the last formula :-) ). I am needing this for a computer program where i am going to "sum" an arbitrary number of parities. – Pam Jan 8 '13 at 20:30
• Thanks a lot all. Great responses and help! – Pam Jan 8 '13 at 22:34