2
$\begingroup$

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]

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Jan 8, 2013 at 19:40
  • $\begingroup$ 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. $\endgroup$
    – Pam
    Jan 8, 2013 at 19:43
  • $\begingroup$ $(\sum_k b_k) \mod 2$. $\endgroup$
    – copper.hat
    Jan 8, 2013 at 19:43
  • $\begingroup$ I don’t know of anything simpler than what I wrote in words and @copper.hat has just given symbolically. $\endgroup$ Jan 8, 2013 at 19:44
  • $\begingroup$ 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. $\endgroup$
    – copper.hat
    Jan 8, 2013 at 19:50

2 Answers 2

1
$\begingroup$

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 $$

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

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} \}$.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Pam
    Jan 8, 2013 at 20:30
  • $\begingroup$ Thanks a lot all. Great responses and help! $\endgroup$
    – Pam
    Jan 8, 2013 at 22:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .