View source for Negative base

{{numeral systems}}
A '''negative base''' (or negative [[radix]]) may be used to construct a [[non-standard positional numeral system]]. Like other place-value systems, each position holds multiples of the appropriate power of the system's base; but that base is negative—that is to say, the base {{mvar|b}} is equal to {{mvar|−r}} for some natural number {{mvar|r}} ({{mvar|r ≥ 2}}).

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.

The common names for negative-base positional numeral systems are formed by [[prefix (linguistics)|prefixing]] ''nega-'' to the name of the corresponding positive-base system; for example, '''negadecimal''' (base −10) corresponds to [[decimal]] (base 10), '''negabinary''' (base −2) to [[binary numeral system|binary]] (base 2), '''negaternary''' (base −3) to [[ternary numeral system|ternary]] (base 3), and '''negaquaternary''' (base −4) to [[quaternary numeral system|quaternary]] (base 4).<ref>{{citation|first=Donald|last=Knuth|title=[[The Art of Computer Programming]], Volume 2|year=1998|edition=3rd|pages=204–205}}. Knuth mentions both negabinary and negadecimal.</ref><ref>The negaternary system is discussed briefly in {{Citation | last1=Petkovšek | first1=Marko | author1-link=Marko Petkovšek | title=Ambiguous numbers are dense | doi=10.2307/2324393 | mr=1048915 | year=1990 | journal=[[American Mathematical Monthly|The American Mathematical Monthly]] | issn=0002-9890 | volume=97 | issue=5 | pages=408–411}}.</ref>

==Example==
Consider what is meant by the representation {{val|fmt=none|12243}} in the negadecimal system, whose base {{mvar|b}} is −10:

{| class="wikitable" style="text-align:center;"
|-
|+ Multiples of
|-
| {{math|(−10)<sup>4</sup> {{=}} 10,000}}
| {{math|(−10)<sup>3</sup> {{=}} −1,000}}
| {{math|(−10)<sup>2</sup> {{=}} 100}}
| {{math|(−10)<sup>1</sup> {{=}} −10}}
| {{math|(−10)<sup>0</sup> {{=}} 1}}
|-
| 1
| 2
| 2
| 4
| 3
|}

Since 10,000 + (−2,000) + 200 + (−40) + 3 = {{val|fmt=commas|8163}}, the representation {{val|fmt=commas|12243|s={{sub|−10}}}} in negadecimal notation is equivalent to {{val|fmt=commas|8,163|s={{sub|10}}}} in decimal notation, while {{val|fmt=commas|−8163|s={{sub|10}}}} in decimal would be written {{val|fmt=commas|9,977|s={{sub|−10}}}} in negadecimal.

==History==
Negative numerical bases were first considered by [[Vittorio Grünwald]] in his work ''Giornale di Matematiche di Battaglini'', published in 1885.<ref>Vittorio Grünwald. ''Giornale di Matematiche di Battaglini'' (1885), 203-221, 367</ref> Grünwald gave algorithms for performing addition, subtraction, multiplication, division, root extraction, divisibility tests, and radix conversion. Negative bases were later independently rediscovered by [[Aubrey J. Kempner|A. J. Kempner]] in 1936<ref>{{citation
 | last = Kempner | first = A. J. | authorlink = Aubrey J. Kempner
 | doi = 10.2307/2300532
 | issue = 10
 | journal = [[American Mathematical Monthly]]
 | mr = 1523792
 | pages = 610–617
 | title = Anormal Systems of Numeration
 | volume = 43
 | year = 1936}}.</ref> and [[Zdzisław Pawlak]] and A. Wakulicz in 1959.<ref>{{citation
 | last1 = Pawlak | first1 = Z.
 | last2 = Wakulicz | first2 = A.
 | journal = Bulletin de l'Académie Polonaise des Sciences |series = Classe III
 | pages = 233–236
 | title = Use of expansions with a negative basis in the arithmometer of a digital computer
 | volume = 5
 | year = 1957}}.</ref>

Negabinary was implemented in the early [[Poland|Polish]] computer [[BINEG]] (and [[UMC (computer)|UMC]]), built 1957–59, based on ideas by Z. Pawlak and A. Lazarkiewicz from the [[Institute of Mathematics of the Polish Academy of Sciences|Mathematical Institute]] in [[Warsaw]].<ref>[http://chc60.fgcu.edu/images/articles/Marczynski.pdf Marczynski, R. W., "The First Seven Years of Polish Computing"] {{webarchive|url=https://web.archive.org/web/20110719192337/http://chc60.fgcu.edu/images/articles/Marczynski.pdf |date=2011-07-19 }}, IEEE Annals of the History of Computing, Vol. 2, No 1, January 1980</ref>  Implementations since then have been rare.

==Notation and use==
Denoting the base as {{mvar|−r}}, every [[integer]] {{mvar|a}} can be written uniquely as
:<math>a = \sum_{i=0}^{n}d_{i}(-r)^{i}</math>
where each digit {{mvar|d<sub>k</sub>}} is an integer from 0 to {{math|''r'' - 1}} and the leading digit {{mvar|d<sub>n</sub>}} is {{math|> 0}} (unless {{math|''n''&#x003D;0}}). The base {{mvar|−r}} expansion of {{mvar|a}} is then given by the string {{math|''d''<sub>''n''</sub>''d''<sub>''n''-1</sub>&hellip;''d''<sub>1</sub>''d''<sub>0</sub>}}.

Negative-base systems may thus be compared to [[signed-digit representation]]s, 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 {{mvar|−r}} as in base {{mvar|r}}.  For example, the numbers from 100 to 109 have the same representations in decimal and negadecimal.  Similarly,
:<math>17=2^4+2^0=(-2)^4+(-2)^0</math>
and is represented by 10001 in binary and 10001 in negabinary.

Some numbers with their expansions in a number of positive and corresponding negative bases are:

{|class="wikitable" style="text-align:right;"
! Decimal !! Negadecimal !! Binary !! Negabinary !! Ternary !! Negaternary !! Balanced Ternary !! Nega Balanced Ternary !! Quaternary !! Negaquaternary
|-
| −15 || 25  || −1111 || 110001 || −120 || 1220 || T110 || 11T0 || −33 || 1301
|-
|   ⋮ ||  ⋮  ||     ⋮ ||      ⋮ ||    ⋮ ||    ⋮ ||   ⋮ ||   ⋮ ||  ⋮ ||   ⋮
|-
|  −5 || 15  ||  −101 ||   1111 ||  −12 ||   21 || T11 || TT1 || −11 || 23
|-
|  −4 || 16  ||  −100 ||   1100 ||  −11 ||   22 || TT || 1T || −10 || 10
|-
|  −3 || 17  ||   −11 ||   1101 ||  −10 ||   10 || T0 || 10 || −3 || 11
|-
|  −2 || 18  ||   −10 ||     10 ||   −2 ||   11 || T1 || 11 || −2 || 12
|-
|  −1 || 19  ||    −1 ||     11 ||   −1 ||   12 || T || T || −1 || 13
|-
|   0 ||  0  ||     0 ||      0 ||    0 ||    0 || 0 || 0 || 0 || 0
|-
|   1 ||  1  ||     1 ||      1 ||    1 ||    1 || 1 || 1 || 1 || 1
|-
|   2 ||  2  ||    10 ||    110 ||    2 ||    2 || 1T || TT || 2 || 2
|-
|   3 ||  3  ||    11 ||    111 ||   10 ||  120 || 10 || T0 || 3 || 3
|-
|   4 ||  4  ||   100 ||    100 ||   11 ||  121 || 11 || T1 || 10 || 130
|-
|   5 ||  5  ||   101 ||    101 ||   12 ||  122 || 1TT || 11T || 11 || 131
|-
|   6 ||  6  ||   110 ||  11010 ||   20 ||  110 || 1T0 || 110 || 12 || 132
|-
|   7 ||  7  ||   111 ||  11011 ||   21 ||  111 || 1T1 || 111 || 13 || 133
|-
|   8 ||  8  ||  1000 ||  11000 ||   22 ||  112 || 10T || 10T || 20 || 120
|-
|   9 ||  9  ||  1001 ||  11001 ||  100 ||  100 || 100 || 100 || 21 || 121
|-
|  10 || 190 ||  1010 ||  11110 ||  101 ||  101 || 101 || 101 || 22 || 122
|-
|  11 || 191 ||  1011 ||  11111 ||  102 ||  102 || 11T || 1TT || 23 || 123
|-
|  12 || 192 ||  1100 ||  11100 ||  110 ||  220 || 110 || 1T0 || 30 || 110
|-
|  13 || 193 ||  1101 ||  11101 ||  111 ||  221 || 111 || 1T1 || 31 || 111
|-
|  14 || 194 ||  1110 ||  10010 ||  112 ||  222 || 1TTT || TT1T || 32 || 112
|-
|  15 || 195 ||  1111 ||  10011 ||  120 ||  210 || 1TT0 || TT10 || 33 || 113
|-
|  16 || 196 || 10000 ||  10000 ||  121 ||  211 || 1TT1 || TT11 || 100 || 100
|-
|  17 || 197 || 10001 ||  10001 ||  122 ||  212 || 1T0T || TT0T || 101 || 101
|-
|  18 || 198 || 10010 ||  10110 ||  200 ||  200 || 1T10 || TTT0 || 102 || 102
|}

Note that, with the exception of nega balanced ternary, the base {{mvar|−r}} expansions of negative integers have an [[even number]] of digits, while the base {{mvar|−r}} expansions of the non-negative integers have an [[odd number]] of digits.

==Calculation==
The base {{mvar|−r}} expansion of a number can be found by repeated division by {{mvar|−r}}, recording the non-negative remainders <math> \in \{0, 1, \ldots, r-1\}</math>, and concatenating those remainders, starting with the last.  Note that if {{math| ''a'' / ''b'' &#x003D; ''c''}}, remainder {{mvar|d}}, then {{math| ''bc'' + ''d'' &#x003D; ''a''}} and therefore {{math| ''d'' &#x003D; ''a'' - ''bc''}}. To arrive at the correct conversion, the value for {{mvar|c}} must be chosen such that {{mvar|d}} is non-negative and minimal. This is exemplified in the fourth line of the following example wherein –5 ÷ –3 must be chosen to equal 2 remainder 1 instead of 1 remainder 2.

For example, to convert 146 in decimal to negaternary:
:<math>\begin{array}{rr}
 146 \div (-3) = & -48 ~\operatorname{remainder}~ 2 \\
 -48 \div (-3) = &  16 ~\operatorname{remainder}~ 0 \\
  16 \div (-3) = &  -5 ~\operatorname{remainder}~ 1 \\
  -5 \div (-3) = &   2 ~\operatorname{remainder}~ 1 \\
   2 \div (-3) = &   0 ~\operatorname{remainder}~ 2
\end{array}</math>
Reading the remainders backward we obtain the negaternary representation of 146<sub>10</sub>: 21102<sub>–3</sub>.
:Proof: ((('''2'''·(–3)+'''1''')·(–3)+'''1''')·(–3)+'''0''')·(–3)+'''2''' = 146<sub>10</sub>.

Note that in most [[programming languages]], the result (in integer arithmetic) of dividing a negative number by a negative number is rounded towards 0, usually leaving a negative remainder. In such a case we have {{math|''a'' &#x003D; (−''r'')''c'' + ''d'' &#x003D; (−''r'')''c'' + ''d'' − ''r'' + ''r'' &#x003D; (−''r'')(''c'' + 1) + (''d'' + ''r'')}}. Because {{math|{{!}}d{{!}} < r}}, {{math|(''d'' + ''r'')}} is the positive remainder. Therefore, to get the correct result in such case, computer implementations of the above algorithm should add 1 and {{mvar|r}} to the quotient and remainder respectively.

=== Example implementation code ===
==== To negabinary ====
===== C# =====
<source lang="csharp">
static string ToNegabinary(int value)
{
	string result = string.Empty;

	while (value != 0)
	{
		int remainder = value % -2;
		value = value / -2;

		if (remainder < 0)
		{
			remainder += 2;
			value += 1;
		}

		result = remainder.ToString() + result;
	}

	return result;
}
</source>
===== C++ =====
<source lang="c++">
auto to_negabinary(int value)
{
    std::bitset<sizeof(int) * CHAR_BIT > result;
    std::size_t bit_position = 0;

    while (value != 0)
    {
        const auto div_result = std::div(value, -2);

        if (div_result.rem < 0)
            value = div_result.quot + 1;
        else
            value = div_result.quot;

        result.set(bit_position, div_result.rem != 0);

        ++bit_position;
    }

    return result;
}
</source>
==== To negaternary ====
===== C# =====
<source lang="csharp">
static string negaternary(int value)
{
	string result = string.Empty;

	while (value != 0)
	{
		int remainder = value % -3;
		value = value / -3;

		if (remainder < 0)
		{
			remainder += 3;
			value += 1;
		}

		result = remainder.ToString() + result;
	}

	return result;
}
</source>

===== [[Visual Basic .NET]] =====
<syntaxhighlight lang="vb.net">
Private Shared Function ToNegaternary(value As Integer) As String
	Dim result As String = String.Empty

	While value <> 0
		Dim remainder As Integer = value Mod -3
		value /= -3

		If remainder < 0 Then
			remainder += 3
			value += 1
		End If

		result = remainder.ToString() & result
	End While

	Return result
End Function
</syntaxhighlight>

===== [[Python (programming language)|Python]] =====
<source lang="python">
def negaternary(i):
    if i == 0:
        digits = ['0']
    else:
        digits = []
        while i != 0:
            i, remainder = divmod(i, -3)
            if remainder < 0:
                i, remainder = i + 1, remainder + 3
            digits.append(str(remainder))
    return ''.join(digits[::-1])
</source>

===== Common Lisp =====
<source lang="lisp">
(defun negaternary (i)
  (if (zerop i)
      "0"
      (let ((digits "")
            (rem 0))
        (loop while (not (zerop i)) do
          (progn
            (multiple-value-setq (i rem) (truncate i -3))
            (when (minusp rem)
              (incf i)
              (incf rem 3))
            (setf digits (concatenate 'string (write-to-string rem) digits))))
        digits)))
</source>

==== To any negative base ====

===== Java =====
<source lang="java">
    public String negativeBase(int integer, int base) {
        String result = "";
        int number = integer;
        while (number != 0) {
            int i = number % base;
            number /= base;
            if(i < 0) {
                i += Math.abs(base);
                number++;
            }

            result = i + result;
        }

        return result;
    }
</source>

===== AutoLisp =====
from [-10 -2] interval:
<syntaxhighlight lang="Lisp">
(defun negabase (num baz / dig rst)
  ;; NUM is any number. BAZ is any number in the interval [-10, -2].
  ;;
  ;; NUM and BAZ will be truncated to an integer if they're floats (e.g. 14.25
  ;; will be truncated to 14, -123456789.87 to -123456789, etc.).
  (if (and (numberp num)
           (numberp baz)
           (<= (fix baz) -2)
           (> (fix baz) -11))
      (progn
        (setq baz (float (fix baz))
              num (float (fix num))
              dig (if (= num 0) "0" ""))
        (while (/= num 0)
               (setq rst (- num (* baz (setq num (fix (/ num baz))))))
               (if (minusp rst)
                   (setq num (1+ num)
                         rst (- rst baz)))
               (setq dig (strcat (itoa (fix rst)) dig)))
        dig)
      (progn
        (prompt
         (cond
           ((and (not (numberp num))
                 (not (numberp baz)))
            "\nWrong number and negabase.")
           ((not (numberp num))
            "\nWrong number.")
           ((not (numberp baz))
            "\nWrong negabase.")
           (t
            "\nNegabase must be inside [-10 -2] interval.")))
        (princ))))
</syntaxhighlight>

===== PHP =====
The conversion from integer to some negative base:
<source lang="php">
function toNegativeBase($no, $base)
{
	$digits = array();
	$base = intval($base);
	while ($no != 0) {
		$temp_no = $no;
		$no = intval($temp_no / $base);
		$remainder = ($temp_no % $base);
 
		if ($remainder < 0) {
			$remainder += abs($base);
			$no++;
		}
 
		array_unshift($digits, $remainder);
	}
 
	return $digits;
}
</source>

===== Visual Basic .NET =====
<syntaxhighlight lang="vb.net">
Function toNegativeBase(Number As Integer , base As Integer) As System.Collections.Generic.List(Of Integer)

	Dim digits As New System.Collections.Generic.List(Of Integer)
	while Number <> 0
		Dim remainder As Integer= Number Mod base
		Number = CInt(Number / base)
 
		if remainder < 0 then
			remainder += system.math.abs(base)
			Number+=1
		end if
 
		digits.Insert(0, remainder)
	end while
 
	return digits
end function
</syntaxhighlight>

=== Shortcut calculation ===
The following algorithms assume that
# the input is available in [[bitstring]]s and coded in (base +2; digits <math>\in \; \{0, 1\}</math>) (as in most today's digital computers),
# there are add (+) and xor (^) operations which operate on such bitstrings (as in most today's digital computers),
# the set <math>D</math> of output digits is standard, i.&nbsp;e. <math>D = \{0, |b|-1\}</math> with base <math>b\in \{-2,-4\}</math>,
# the output is coded in the same bitstring format, but the meaning of the places is another one.

====To negabinary====
The conversion to ''negabinary'' (base −2; digits <math>\in \; \{0, 1\}</math>) allows a remarkable shortcut 
(C implementation):
<source lang="c">
unsigned int toNegaBinary(unsigned int value) // input in standard binary
{
	unsigned int Schroeppel2 = 0xAAAAAAAA; // = 2/3*((2*2)^16-1) = ...1010
	return (value + Schroeppel2) ^ Schroeppel2; // eXclusive OR
	// resulting unsigned int to be interpreted as string of elements ε {0,1} (bits)
}
</source>

Due to D. Librik (Szudzik). The bitwise XOR portion is originally due to [[Richard Schroeppel|Schroeppel]] (1972).<ref>See the MathWorld Negabinary link</ref>

JavaScript port for the same shortcut calculation: 
<source lang="javascript">
function toNegaBinary( number ) {
    var Schroeppel2 = 0xAAAAAAAA;
    // Convert to NegaBinary String
    return ( ( number + Schroeppel2 ) ^ Schroeppel2 ).toString(2);
}
</source>

====To negaquaternary====
The conversion to ''negaquaternary'' (base −4; digits <math>\in \; \{0, 1, 2, 3\}</math>) allows a similar shortcut (C implementation):
<source lang="c">
unsigned int toNegaQuaternary(unsigned int value) // input in standard binary
{
	unsigned int Schroeppel4 = 0xCCCCCCCC; // = 4/5*((2*4)^8-1) = ...11001100 = ...3030
	return (value + Schroeppel4) ^ Schroeppel4; // eXclusive OR
	// resulting unsigned int to be interpreted as string of elements ε {0,1,2,3} (pairs of bits)
}
</source>

JavaScript port for the same shortcut calculation: 
<source lang="javascript">
function toNegaQuaternary( number ) {
    var Schroeppel4 = 0xCCCCCCCC;
    // Convert to NegaQuaternary String
    return ( ( number + Schroeppel4 ) ^ Schroeppel4 ).toString(4);
}
</source>

==Arithmetic operations==
The following describes the arithmetic operations for negabinary; calculations in larger bases are similar.

===Addition===
Adding negabinary numbers proceeds bitwise, starting from the [[least significant bit]]s; the bits from each addend are summed with the ([[balanced ternary]]) carry from the previous bit (0 at the LSB). This sum is then decomposed into an output bit and carry for the next iteration as show in the table:

{| class="wikitable" style="text-align:right;"
! colspan=2 rowspan=2 | Sum
! colspan=3 | Output
! rowspan=2 | Comment 
|-
! Bit
! colspan=2 | Carry
|-
| −2 || 010{{sub|−2}} || 0 ||  1 || 01{{sub|−2}}
| style="text-align:left;" | −2 occurs only during subtraction.
|-
| −1 || 011{{sub|−2}} || 1 ||  1 || 01{{sub|−2}}
| style="text-align:left;" |
|-
|  0 || 000{{sub|−2}} || 0 ||  0 || 00{{sub|−2}}
| style="text-align:left;" |
|-
|  1 || 001{{sub|−2}} || 1 ||  0 || 00{{sub|−2}}
| style="text-align:left;" |
|-
|  2 || 110{{sub|−2}} || 0 || −1 || 11{{sub|−2}}
| style="text-align:left;" |
|-
|  3 || 111{{sub|−2}} || 1 || −1 || 11{{sub|−2}}
| style="text-align:left;" | 3 occurs only 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.

As an example, to add 1010101{{sub|−2}} (1 + 4 + 16 + 64 = 85) and 1110100{{sub|−2}} (4 + 16 − 32 + 64 = 52),

 Carry:          1 −1  0 −1  1 −1  0  0  0
 First addend:         1  0  1  0  1  0  1
 Second addend:        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{{sub|−2}} (1 − 8 + 16 − 128 + 256 = 137).

==== Another method ====
While adding two negabinary numbers, every time a carry is generated an extra carry should be propagated to next bit. Consider same example as above

 Extra carry:       1  1  0  1  0  0  0     
 Carry:          1  0  1  1  0  1  0  0  0
 First addend:         1  0  1  0  1  0  1
 Second addend:        1  1  1  0  1  0  0 +
                --------------------------
 Answer:         1  1  0  0  1  1  0  0  1

==== Negabinary full adder ====
A [[Adder (electronics)|full adder]] circuit can be designed to add numbers in negabinary. The following logic is used to calculate the sum and carries:<ref>{{cite book |last=Francis, Suganda, Shizuhuo |first=Yu, Jutamulia, Yin |date=4 September 2001 |title=Introduction to Information Optics |publisher=Academic Press |page=498 |isbn=9780127748115}}</ref>

:<math>s_i = a_i \oplus b_i \oplus c_i^+ \oplus c_i^-</math>

:<math>c_{i+1}^+ = \overline{a_i}\overline{b_i}\overline{c_i^+}c_i^-</math>

:<math>c_{i+1}^- = a_i b_i \overline{c_i^-} + (a_i \oplus b_i)c_i^+ \overline{c_i^-}</math>

==== Incrementing negabinary numbers ====
Incrementing a negabinary number can be done by using the following formula:<ref>{{cite web |url=https://math.stackexchange.com/q/1878151 |title=Archived copy |accessdate=2016-08-29 |url-status=live }}</ref>

:<math>2x \oplus ((2x \oplus x) + 1)</math>

===Subtraction===
To subtract, multiply each bit of the second number by −1, and add the numbers, using the same table as above.

As an example, to compute 1101001{{sub|−2}} (1 − 8 − 32 + 64 = 25) minus 1110100{{sub|−2}} (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{{sub|−2}} (1 + 4 −32 = −27).

Unary negation, {{math|−''x''}}, can be computed as binary subtraction from zero, {{math|0 − ''x''}}.

===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 numeral system|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 −1 −1 −1  0 −1  0  0
 Number:       1  0  2  1  2  2  2  3  2  0  2  1  0
 Bit (result): 1  0  0  1  0  0  0  1  0  0  0  1  0
 Carry:           0 −1  0 −1 −1 −1 −1 −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.

===Comparing negabinary numbers===
It is possible to compare negabinary numbers by slightly adjusting a normal unsigned [[digital comparator|binary comparator]]. When comparing the numbers <math>A</math> and <math>B</math>, invert each odd positioned bit of both numbers.
After this, compare <math>A</math> and <math>B</math> using a standard unsigned comparator.<ref>{{Cite journal |doi = 10.1049/ij-ecs.1977.0005|title = Negabinary arithmetic circuits using binary arithmetic|journal = IEE Journal on Electronic Circuits and Systems|volume = 1|issue = 2|pages = 77|year = 1977|last1 = Murugesan|first1 = San}}</ref>
<!--
 (Todo: Division by arbitrary numbers?)
 --><!--

"To be written things", like below, better be written. Empty sections are ugly. 
===Divisibility tests===
To be written.

===Root extraction===
To be written.

-->

==Fractional numbers==
Base {{mvar|−r}} representation may of course be carried beyond the [[radix point]], allowing the representation of non-integral numbers.

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.

===Non-unique representations===
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.  However, there do exist rationals with non-unique representations. For the digits {0, 1, &hellip;, '''t'''} with <math>\mathbf{t}:=r\!-\!\!1=-b\!-\!\!1</math> the biggest digit and
:<math>T:=0.\overline{01}_b = \sum_{i=1}^{\infty} b^{-2i} = \frac1{b^2-1} = \frac1{r^2-1}</math>
we have
:<math>0.\overline{0\mathbf{t}}_b=\mathbf{t}T=\frac{r\!-\!\!1}{r^2-1}=\frac1{r+1}</math> &nbsp; &nbsp; as well as
:<math>1.\overline{\mathbf{t}0}_b = 1+\mathbf{t}bT = \frac{(r^2-1)+(r\!-\!\!1)b}{r^2-1}= \frac1{r+1}.</math>
So every number <math>\frac1{r+1}+z</math> with a [[Positional notation#Terminating fractions|terminating fraction]] <math>z\in \Z r^{\Z}</math> added has two distinct representations.

For example, in negaternary, i.e. <math>b=-3</math> and <math>\mathbf{t}=2</math>, there is
: <math>1.\overline{02}_{(-3)} = \frac{5}{4} = 2.\overline{20}_{(-3)}</math>.

Such non-unique representations can be found by considering the largest and smallest possible representations with integral parts 0 and 1 respectively, and then noting that they are equal. (Indeed, this works with any integral-base system.) The rationals thus non-uniquely expressible are those of form
: <math>\frac{z(r+1) + 1}{b^i(r + 1)}</math>
with <math>z,i\in \Z.</math>

== Imaginary base ==
{{main|Complex-base system}}

Just as using a negative base allows the representation of negative numbers without an explicit negative sign, using an [[imaginary number|imaginary]] base allows the representation of [[Gaussian integer]]s. [[Donald Knuth]] proposed the [[quater-imaginary base]] (base 2i) in 1955.<ref>D. Knuth. The Art of Computer Programming. Volume 2, 3rd Edition. Addison-Wesley. pp. 205, "Positional Number Systems"</ref>

== See also ==
* [[Quater-imaginary base]]
* [[Binary numeral system|Binary]]
* [[Balanced ternary]]
* [[Quaternary numeral system]]
* [[Numeral system]]s

==References==
{{reflist|30em}}

==Further reading==
*{{cite book |title=Hacker's Delight |title-link=Hacker's Delight |first=Henry S. |last=Warren Jr. |date=2013 |orig-year=2002 |edition=2 |publisher=[[Addison Wesley]] - [[Pearson Education, Inc.]] |isbn=978-0-321-84268-8 |id=0-321-84268-5}}

==External links==
*{{mathworld|title=Negabinary|urlname=Negabinary}}
*{{mathworld|title=Negadecimal|urlname=Negadecimal}}

[[Category:Non-standard positional numeral systems]]
[[Category:Computer arithmetic]]
[[Category:Negative concepts]]