|
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
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).
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.
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?)
See also binary, balanced ternary, numeral system.
wikipedia.org dumped 2003-03-17 with terodump