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$ – Brian M. Scott Jan 8 '13 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 '13 at 19:43
  • $\begingroup$ $(\sum_k b_k) \mod 2$. $\endgroup$ – copper.hat Jan 8 '13 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$ – Brian M. Scott Jan 8 '13 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 '13 at 19:50
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 '13 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 '13 at 20:30
  • $\begingroup$ Thanks a lot all. Great responses and help! $\endgroup$ – Pam Jan 8 '13 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.