Negabinary base

The negabinary base, and in general any negative-base system, allows the representation of negative numbers without the need of using a minus sign.

Calculation by hand

To get some intuition about how this works, let’s consider the negabinary base (). In this base, each position represents a power of :

and therefore:

4-2
4-2+1

4+1
16-8-2

-2+1

-8+4+1
-8+4
-8+4-2+1
-8+4-2

Algorithm implementation

Binary expansion

Before jumping into the implementation of the negabinary representation, it’s worth reviewing the algorithm to get the binary expansion of a decimal number:

def binary_expansion(n):
    """
    Binary representation of n
    MSB (most significant bit) is in the leftmost position
    """
    b = 2
    digits = []
    while n > 0:
        n, r = divmod(n, b)
        digits.append(str(r))
    return "".join(digits[::-1])

This function is valid for any such that (for new symbols are needed in addition to the numeric ones).

Now, can we use the same algorithm for ? Let’s take a closer look.

The above algorithm relies on an implementation detail of the programming language, namely: for the result of the integer division is rounded towards zero and that makes the remainder positive.

Let that sink in and take a look at this other post Do you really know how to use the modulo operator?

Different programming languages behave differently when calculating the integer division: Python performs a floored division that returns the largest integer less than or equal to the quotient, whereas Java does a truncated division that returns the integer part of the quotient.

When dividend and divisor are positive, then both divisions are equivalent, resulting in the quotient being rounded towards zero.

Negabinary expansion

Things are different in the realm of negative numbers though. For instance,

//Use case: positive number in negabinary

//Python
7/(-2) = (-4, -1)

//Java
7/(-2) = (-3, 1)

//Use case: negative number in negabinary

//Python
-7/(-2) = (3, -1)

//Java
-7/(-2) = (3, -1)

As a picture is worth a thousand words, here’s the above explanation in images.

1. truncated division when dividend is positive
2. floored division when dividend is positive
3. division when dividend is negative, both divisions are equivalent

In order to avoid negative digits in the negabinary representation, we need to turn the remainders into positive values. According to the previous picture, that can be achieved by adding 1 to the quotient and subtracting the base from the remainder.

And now we are equipped to implement the algorithm of the negabinary expansion:

def negabinary_expansion(n):
    """
    Negabinary (base -2) representation of n
    MSB (most significant bit) is in the leftmost position
    """
    b = -2
    digits = []
    while n != 0:
        n, r = divmod(n, b)
        if r < 0:
            r -= b
            n += 1
        digits.append(str(r))
    return "".join(digits[::-1])