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?

  • 1
    Is $x$ an integer? Rational? Real? Does it matter? $1=(-2)^0$ so its presence in the formula suggests that perhaps $x$ is supposed to be an integer. – John Wayland Bales Aug 1 '16 at 19:31
  • 1
    What do $\oplus$ and $+$ represent? – Henry Aug 1 '16 at 19:33
  • 1
    @Henry Good point. For that matter, what does $2x$ mean? Is a right shift in negabinary equivalent to multiplication by $2$? It would seem not. – John Wayland Bales Aug 1 '16 at 19:40
  • 1
    @JohnWaylandBales Indeed multiplication by two seems a little complicated: three is $111_{-2}^{ }$, negative six is $1110_{-2}^{ }$, twelve is $11100_{-2}^{ }$, but six is $11010_{-2}^{ }$ – Henry Aug 1 '16 at 19:51
  • 1
    @Henry Right shift would have to be equivalent to multiplication by $(-2)$ so I would assume that $2x$ is the double of $x$. Most of the research seems to be paywalled and I lost my library privileges when I retired (as full professor with 39 years at my institution. Go figure.) – John Wayland Bales Aug 1 '16 at 20:03
up vote 3 down vote accepted
+100

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$

  • +1, finally had a chance to read through this. Hidden in the middle there is a good description of how incrementing works in negabinary: If you increment a $1$ you carry a decrement to the next place, and if you decrement a $0$ you carry an increment to the next place. – 6005 Aug 11 '16 at 6:14

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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