Negabinary

'Negabinary' (radix -2) is a non-standard positional numeral system used in the experimental Polish computers SKRZAT 1 and BINEG in 1950. It has the unusual property that negative and positive numbers can be represented without a sign bit, although arithmetic operations are more complicated.

History

Negative numerical bases were discovered by Vittorio Grunwald in his work Giornale di Matematiche di Battaglini, published in 1885. Grunwald gave algorithms for performing addition, subtraction, multiplication, division, root extraction, divisibility tests, and radix conversion. Negative bases were later independently rediscovered by A. J. Kempner in 1936 and Z. Pawlak and A. Wakulicz in 1959.

Writing numbers in negabinary

Every integer can be written uniquely in the form

$\sum _{k=0}^{n}d_{k}(-2)^{k}$

where each digit d_k is either 0 or 1 and the "leading bit" d_n is 1 (unless n=0). The negabinary expansion of the given integer is then given by the string d_n;d_n-1...d₁d₀. Some negabinary numbers have the same representation in binary. For example,

$17=4^{2}+4^{0}$

and is represented by 10001 in binary and 10001 in negabinary.

The numbers from -5 to 6 with their negabinary expansions are:

-5  1111
-4  1100
-3  1101
-2    10
-1    11
 0     0
 1     1
 2   110
 3   111
 4   100
 5   101
 6 11010

The negabinary expansion of a number can be found by repeated division by -2, recording the non-negative remainders of 0 or 1, and concatenating those remainders, starting with the last. Note that if a / b = c, remainder d, then bc + d = a. For example:

13 / -2 = -6, remainder 1
-6 / -2 =  3, remainder 0
 3 / -2 = -1, remainder 1
-1 / -2 =  1, remainder 1
 1 / -2 =  0, remainder 1

Therefore, the negabinary expansion of 13 is 11101.

Note that the negabinary expansions of negative integers have an even number of bits, while the negabinary expansions of the non-negative integers have an odd number of bits.

Addition

To add two negabinary numbers, start with a carry of 0, and, starting from the least significant bits, add the bits of the two numbers plus the carry. The resulting number is then looked up in the following table to get the bit to write down as result, and the next carry:

number bit carry
  -2    0    1    (Note: -2 occurs only during subtraction.)
  -1    1    1
   0    0    0
   1    1    0
   2    0   -1
   3    1   -1    (Note: 3 occurs only during addition.)

The second row of this table, for instance, expresses the fact that -1 = 1 + 1×(-2); the fifth row says 2 = 0 + -1×(-2); etc.

As an example, to add 1010101 (1+4+16+64 = 85) and 1110100 (4+16-32+64 = 52),

carry:          1 -1  0 -1  1 -1  0  0  0
first number:         1  0  1  0  1  0  1
second number:        1  1  1  0  1  0  0 +
               --------------------------
number:         1 -1  2  0  3 -1  2  0  1
bit (result):   1  1  0  0  1  1  0  0  1
carry:          0  1 -1  0 -1  1 -1  0  0

so the result is 110011001 (1-8+16-128+256 = 137).

Subtraction

To subtract, multiply each bit of the second number by -1, and add the numbers, using the same table as above.

As an example, to compute 1101001 (1-8-32+64 = 25) minus 1110100 (4+16-32+64 = 52),

carry:          0  1 -1  1  0  0  0
first number:   1  1  0  1  0  0  1
second number: -1 -1 -1  0 -1  0  0 +
               --------------------
number:         0  1 -2  2 -1  0  1
bit (result):   0  1  0  0  1  0  1
carry:          0  0  1 -1  1  0  0

so the result is 100101 (1+4-32 = -27).

To negate a number, compute 0 minus the number.

Multiplication and division

Shifting to the left multiplies by -2, shifting to the right divides by -2.

To multiply, multiply like normal decimal or binary numbers, but using the negabinary rules for adding the carry, when adding the numbers.

first number:                   1  1  1  0  1  1  0
second number:                  1  0  1  1  0  1  1 *
              -------------------------------------
                                1  1  1  0  1  1  0
                             1  1  1  0  1  1  0

                       1  1  1  0  1  1  0
                    1  1  1  0  1  1  0

              1  1  1  0  1  1  0                   +
              -------------------------------------
carry:        0 -1  0 -1 -1 -1 -1 -1  0 -1  0  0
number:       1  0  2  1  2  2  2  3  2  0  2  1  0
bit (result): 1  0  0  1  0  0  0  1  0  0  0  1  0
carry:           0 -1  0 -1 -1 -1 -1 -1  0 -1  0  0

For each column, add carry to number, and divide the sum by -2, to get the new carry, and the resulting bit as the remainder.

See also binary, balanced ternary and negaternary numeral systems.

External resources

• Vittorio Grunwald. Giornale di Matematiche di Battaglini (1885), 203-221, 367
• A. J. Kempner. (1936), 610-617
• Z. Pawlek and A. Wakulicz Bulletin de l'Academie Polonaise des Scienses, Classe III, 5 (1957), 233-236; Serie des sciences techniques 7 (1959), 713-721
• L. Wadel IRE Transactions EC-6 1957, 123
• N. M. Blachman, Communications of the ACM (1961), 257
• IEEE Transactions 1963, 274-276
• Computer Design May 1967, 52-63
• R. W. Marczynski, Annotated History of Computing, 1980, 37-48
• D. Knuth. The Art of Computer Programming, Volume 2, 3rd. Ed. pp204-205