# Get A⊕(B+1) from A⊕B

I have numbers A,B,C.D.

(⊕ is XOR)

C = A⊕B

D = A⊕(B+1)

Is there any way to get D from C, when I do not know A and B? How?

Thanks for help!

-
What does ⊕ mean? – Chris Eagle Mar 16 '13 at 14:31
It means XORing bit by bit, edited question – Tomáš Šíma Mar 16 '13 at 14:32

This is not possible. For example, suppose $A=B=0$. Then $C=0\oplus 0=0$, while $D=0 \oplus 1=1$. But if $A=B=1$, then we still have $C=0$, but now $D=1 \oplus 10=11$. Since one value of $C$ can correspond to two different values of $D$, $D$ cannot be deduced from $C$.

-
Ahh, I see. Thanks! Are two different values the maximum I can get? Can I get three(or more) different values of D for one C? – Tomáš Šíma Mar 16 '13 at 14:39
@TomášŠíma: Have you tried checking any examples at all? – Chris Eagle Mar 16 '13 at 14:44
That was stupid comment, I see now. – Tomáš Šíma Mar 16 '13 at 14:45

As Chris explains, you cannot find $D$ exactly.

However, you can narrow down the possible values for $D$ considerably, which can be important in some contexts (such as cryptography).

$B+1$ always differs from $B$ in that a number of least significant bits have been flipped. No bit that is flipped is to the left of any bit that is preserved. This description carries over when you xor with the unknown $A$. So you can say that $D$ must be $C\oplus(2^n-1)$ for some $n\ge 1$.

(It is also easy to see that each of these values is in fact a possible value for $D$, given appropriate choice of $A$, no matter what $C$ is).

-
I solve this in relation to cryptography. In my example n<=8, so the cipher can be bruteforced easily. Thanks a lot! – Tomáš Šíma Mar 16 '13 at 14:51