Negative-base systems can accommodate all the same numbers as standard place-value systems, but both positive and negative numbers are represented without the use of a minus sign (or, in computer representation, a sign bit); this advantage is countered by an increased complexity of arithmetic operations.
The need to store the information normally contained by a negative sign often results in a negative-base number being one digit longer than its positive-base equivalent.
Negative bases were later mentioned in passing by A. J. Kempner in 1936[4] and studied in more detail by Zdzisław Pawlak and A. Wakulicz in 1957.
[5] Negabinary was implemented in the early Polish computer BINEG (and UMC), built 1957–59, based on ideas by Z. Pawlak and A. Lazarkiewicz from the Mathematical Institute in Warsaw.
zfp, a floating-point compression algorithm from the Lawrence Livermore National Laboratory, uses negabinary to store numbers.
According to zfp's documentation:[7] Unlike sign-magnitude representations, the leftmost one-bit in negabinary simultaneously encodes the sign and approximate magnitude of a number.
Moreover, unlike two’s complement, numbers small in magnitude have many leading zeros in negabinary regardless of sign, which facilitates encoding.Denoting the base as −r, every integer a can be written uniquely as where each digit dk is an integer from 0 to r − 1 and the leading digit dn > 0 (unless n = 0).
Negative-base systems may thus be compared to signed-digit representations, such as balanced ternary, where the radix is positive but the digits are taken from a partially negative range.
(In the table below the digit of value −1 is written as the single character T.) Some numbers have the same representation in base −r as in base r. For example, the numbers from 100 to 109 have the same representations in decimal and negadecimal.
The base −r expansion of a number can be found by repeated division by −r, recording the non-negative remainders in
To arrive at the correct conversion, the value for c must be chosen such that d is non-negative and minimal.
Reading the remainders forward we can obtain the negaternary least-significant-digit-first representation.
Therefore, to get the correct result in such case, computer implementations of the above algorithm should add 1 and r to the quotient and remainder respectively.
The above gives the result in an ArrayList of integers, so that the code does not have to handle how to represent a base smaller than -10.
To display the result as a string, one can decide on a mapping of base to characrters.
For example: The following algorithms assume that The conversion to negabinary (base −2; digits in
) allows a similar shortcut (C implementation): JavaScript port for the same shortcut calculation: The following describes the arithmetic operations for negabinary; calculations in larger bases are similar.
This sum is then decomposed into an output bit and carry for the next iteration as show in the table: 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.
Consider same example as above A full adder circuit can be designed to add numbers in negabinary.
The following logic is used to calculate the sum and carries:[9] Incrementing a negabinary number can be done by using the following formula:[10] (The operations in this formula are to be interpreted as operations on regular binary numbers.
Unary negation, −x, can be computed as binary subtraction from zero, 0 − x.
As with positive-base systems, terminating representations correspond to fractions where the denominator is a power of the base; repeating representations correspond to other rationals, and for the same reason.
Unlike positive-base systems, where integers and terminating fractions have non-unique representations (for example, in decimal 0.999... = 1) in negative-base systems the integers have only a single representation.