Let $k$ be an $n$-bit string denoting a natural number. Let $1$ denote the $n$-bit string consisting of all $0$’s except a $1$ at the end, and let $2$ denote the $n$-bit string consisting of all $0$’s except for $1$ at the second to last place. Let $\oplus$ denote bitwise XOR, and let $+$ denote natural number addition. Then my question is, under what circumstances does $((k\oplus 1) + 1) \oplus 1 = (k+1) \oplus 2$?
This question arose in the context of writing a cryptography proof; my proof hinges on the assumption that a randomly chosen $n$-bit string $k$ has a very small probability of satisfying this equation.
If $k$ is even, then $k \oplus 1 = k+1$, while if $k$ is odd, $k \oplus 1 = k-1$. This is seen simply by XORing the digit in the $1$s place with $1$.
This means that if $k$ is even, the LHS evaluates to $(k+1+1) \oplus 1 = k+3$.
If $k$ is odd, then the LHS evaluates to $(k-1+1) \oplus 1 = k \oplus 1 = k-1$.
If there is a $0$ in the $2$s place in the binary expansion of $n=k+1$, then $n \oplus 2 = n+2$. If there is a $1$ instead, then $n \oplus 2 = n-2$. Note that there is a $0$ if $n \mod 4 \in \{0, 1\}$, or equivalently if $k \mod 4 \in \{ 3, 0 \}$.
Making a chart based off the mod $4$ value of $k$ yields $$ \left( \begin{array}{ccc} k\mod 4 & ((k\oplus 1) + 1) \oplus 1 & (k+1)\oplus 2\\ 0 & k+3 & k+1+2=k+3\\ 1 & k-1 & k+1-2=k-1\\ 2 & k+3 & k+1-2=k-1\\ 3 & k-1 & k+1+2=k+3 \end{array} \right) $$
As you can see, they are only equivalent for $k \mod 4 \in \{0, 1\}$