In a file I have written the following formula that increments a negabinary number (a number in base -2):
$$2x \oplus ((2x \oplus x) + 1) $$
In this formula $x$ is a negabinary number interpreted as a binary number and we will perform binary operations on it. $2x$ is a simple binary left shift (110 becomes 1100). $\oplus$ is the XOR operator. The $+1$ is also done using binary addition. The final result is then interpreted as a negabinary number.
Negabinary is of the form $a=\sum_{i=0}^{n}{d_i(-2)^{i}}$ where $d_i\in\left\{0,1\right\}$
For example: $3=4-2+1=111_{-2}$
So, using the formula: when we for example increment $5$ ($101_{-2}$ in negabinary) we get (using binary representation)
$$1010 \oplus ((1010 \oplus 101) + 1)=1010 \oplus (1111 + 1)=1010 \oplus 10000=11010$$
which is 6 in negabinary ($16-8-2$).
The rules of the $\oplus$ operator are:
$0 \oplus 0 = 0$
$0 \oplus 1 = 1$
$1 \oplus 0 = 1$
$1 \oplus 1 = 0$
For multi-bit numbers, the $\oplus$ operation is done by applying these rules on the n-th bit of both operands. For example:
$1101 \oplus 0110 =1011$
I fail to find the original paper where I found this formula. Can anyone explain why this works?
When you add $1$ to a binary number $n$, you just change $k(n)$ binary digits at the end of the number where $k(n)$ is the number of consecutives $1$s at the end of $n$, plus $1$.
And so $n + 1 = n \oplus K(n)$ where $K(n) = (2^{k(n)} - 1)$.
Now your strange operation is $x \mapsto 2x \oplus ((2x \oplus x) + 1) = 2x \oplus (2x \oplus x \oplus K(2x \oplus x)) = x \oplus K(2x \oplus x)$, so from $x$ you just switch the last $k(2x \oplus x)$ binary digits of $x$.
$k(2x \oplus x)-1$ is the number of $1$s at the right of $2x \oplus x$, so those are the number of consecutive digit changes at the right of $x$ :
For example, $101$ has $4$ consecutive digit changes (don't forget about the invisible zeroes on both sides), so you switch $5$ digits to get $11010$.
$11010$ has $0$ consecutive digit changes (because its rightmost digit is a $0$), so you switch $1$ digit to get its successor $11011$. Then, there is $1$ change, so you get $11000$ and so on.
Define $f$ and $g$ recursively on strings of binary digits by :
$f(x0) = x1 , f(x1) = g(x)0 \\ g(x0) = f(x)1, g(x1) = x0$
You should be able to recognize that your operation is simply applying $f$ to the string of binary digits. We need one auxiliary function because we need the memory of what the previous digit was to compare it to the current digit and see if we continue to switch or not.
When you interpret the strings as numbers in base $-2$, those functions become defined by :
$f(-2x+0) = -2x+1 , f(-2x+1) = -2g(x)+0 \\ g(-2x+0) = -2f(x)+1, g(-2x+1) = -2x+0$
Finally, a recursion (on the number of $-2$ary digits of $x$) shows that $f(x) = x+1$ and $g(x)=x-1$ for all $x \in \Bbb Z$