Main Page | See live article | Alphabetical index

Negabinary

'Negabinary' (radix -2) is a fairly obscure numeral system used in the experimental Poland 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.

Table of contents
1 History
2 Writing numbers in negabinary
3 Addition
4 Subtraction
5 Multiplication and Division
6 Divisibility Tests
7 Root Extraction
8 External Resources

History

Negative numerical bases where 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 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
where each digit dk is either 0 or 1 and the "leading bit" dn is 1 (unless n=0). The negabinary expansion of the given integer is then given by the string dn;dn-1...d1d0.

The numbers from -5 to 5 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 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 only occurs during subtraction.)
  -1    1    1
   0    0    0
   1    1    0
   2    0   -1
   3    1   -1    (Note: 3 only occurs 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  0 -2 -1  0 -1  0  0
number:       1  1  2  2  3  3  3  4  2  1  2  1  0
bit (result): 1  0  0  1  0  1  1  1  0  0  0  1  0
carry:           0 -1  0 -1 -1  0 -2 -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.

(TODO: Division by arbitrary numbers?)

Divisibility Tests

To be written.

Root Extraction

To be written.

See also binary, balanced ternary, numeral system.

External Resources