'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 |
|
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
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 11010The 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 1Therefore, 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.
As an example, to add 1010101 (1+4+16+64 = 85) and 1110100 (4+16-32+64 = 52),
As an example, to compute 1101001 (1-8-32+64 = 25) minus 1110100 (4+16-32+64 = 52),
To negate a number, compute 0 minus the number.
To multiply, multiply like normal decimal or binary numbers, but using the negabinary rules for adding the carry, when adding the numbers.
(TODO: Division by arbitrary numbers?)
See also binary, balanced ternary, numeral system.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.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 0so 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.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 0so the result is 100101 (1+4-32 = -27)Multiplication and Division
Shifting to the left multiplies by -2, shifting to the right divides by -2.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 0For each column, add carry to number, and divide the sum by -2, to get the new carry, and the resulting bit as the remainder.Divisibility Tests
To be written.Root Extraction
To be written.
