
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_{2}d_{1}d_{0}, where d_{something} is a digit 0 or 1, is equal to
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 1Therefore, 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+1632+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 (18+16128+256 = 137).
Subtraction To subtract, multiply each bit of the second number by 1, and add the numbers.
As an example, to compute 1101001 (1832+64 = 25) minus 1110100 (4+1632+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+432 = 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.
Search Encyclopedia

Featured Article
