Encyclopedia > Negabinary

  Article Content

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

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 dx...d2d1d0, where dsomething 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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Kuru Kuru Kururin

... collect, record times to beat, and a gold star for getting through the level without any accidents. Kururin was released in Japan and Europe but not in the United ...

 
 
 
This page was created in 38.1 ms