# 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. Jan 8, 2013 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, 2013 at 19:43
• $(\sum_k b_k) \mod 2$. Jan 8, 2013 at 19:43
• I don’t know of anything simpler than what I wrote in words and @copper.hat has just given symbolically. Jan 8, 2013 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. Jan 8, 2013 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, 2013 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, 2013 at 20:30
• Thanks a lot all. Great responses and help!
– Pam
Jan 8, 2013 at 22:34