Tell me more ×
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.
up vote 0 down vote favorite

I want to XOR the password (0x3d), byte by byte, with 0x42, then 0x51, then 0xF7, then 0x6F. this would give me 0xb6..... But, Is there a shortcut to this operation?

share|improve this question
I know there is a shortcut because I saw it before but I forgot how it was??? :) – jjitti Apr 21 '12 at 19:31
Xor is associative : if + denote the xor operation, (a + b) + c = a + (b + c). – Lierre Apr 21 '12 at 19:32
The tags don't fit the question at all. – Fernando Martin Apr 21 '12 at 19:35
Is there a reason why you mentioned AND in the title? – sdcvvc Apr 21 '12 at 19:41
@FernandoMartin — It was firstly “number-theory elementary-number-theory algebraic-number-theory”, and I retagged it as “algebra-precalculus” because it is only symbol manipulation. I'm not sure “logic computer-science” is much better. There should be a tag “elementary-maths”. – Lierre Apr 21 '12 at 19:55

2 Answers

up vote 1 down vote

XOR is associative. Therefore, denoting XOR by ^, you can do

>>> 0x3D ^ 0x42 ^ 0x51 ^ 0xF7 ^ 0x6F
182

but also

>>> 0x3D ^ (0x42 ^ 0x51 ^ 0xF7 ^ 0x6F)
182

which is

>>> 0x3D ^ 0x8B
182

So you can XOR with 0x8B instead. In other words, "multiple xor" is equivalent to a single one.

Associativity follows because XOR is associative on each bit.

share|improve this answer
Thank you for answering. However, your answer is not what I am looking for. What I am looking for is that the operation above can be reduced using AND operation. I am looking for how to use AND to shortcut this operation... Thanks – jjitti Apr 21 '12 at 22:06
@jjitti: using AND only, it is impossible, because AND is monotonic while XOR is not. If you want to express XOR with AND and NOT, then use Fernando's answer. Otherwise I don't know what do you want to do. – sdcvvc Apr 21 '12 at 22:13
up vote -1 down vote

(p XOR q) = (¬p AND q) OR (p AND ¬q), if that was what you were asking.

share|improve this answer
$A \operatorname{xor}{B} = (\lnot A \land B) \lor (A \land \lnot B)$ – Matt N. Apr 21 '12 at 19:37
Indeed, I mixed them up. Thanks Matt! – Fernando Martin Apr 21 '12 at 19:41
Thank you for answering. However, your answer is not what I am looking for. What I am looking for is that the operation above can be reduced using AND operation. I am looking for how to use AND to shortcut this operation... Thanks – jjitti Apr 21 '12 at 22:06

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.