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 Radix Conversion 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.

Radix Conversion The number d_x...d₂d₁d₀, where d_something is a digit 0 or 1, is equal to

<math>\sum_{n=0}^{x}d_{n}(-2)^{n}</math>

The numbers from -5 to 5 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

(Note that 0 and the positive numbers have an odd number of bits, the negative numbers an even number of bits.)

Numbers can be convered to negabinary by repeated division by -2, recording the remainder of 0 or 1. 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, 13 is 11101_-2

Addition To add two negabinary numbers, start with a carry of 0, and, starting from the least significant bits[?], add the bit of each number plus the carry, record the bit of the resulting number and set the carry according to the number. Following is a table of the possible numbers, and what the bit and carry should be.

 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.)

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.

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

• 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, Annoated History of Computing, 1980, 37-48
• D. Knuth. The Art of Computer Programming, Volume 2, 3rd. Ed. pp204-205