Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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]

share|improve this question
    
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
show 1 more comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
    
Very neat. Looks like an "indicator" function for the number of $b$'s to be odd. –  Pam Jan 8 '13 at 21:02
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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