Balanced Ternary

Base 3 with digits $\{-1,0,+1\}$ instead of $\{0,1,2\}$. Every integer — positive or negative — has a unique representation, with no sign needed.

$n={\sum }_i{d}_i{3}^i,d_i\in \{-1,0,1\}.$

Conversion

vector<int> toBalancedTernary(long long n) {
    vector<int> d;
    while (n) {
        int r = ((n % 3) + 3) % 3;
        if (r == 2) { d.push_back(-1); n = (n + 1) / 3; }   // 2 -> -1, carry +1
        else        { d.push_back(r);  n = (n - r) / 3; }
        // careful with negatives: use floor division
    }
    return d;                                               // least significant first
}

The rule: take $n\mathrm{mod}3$; if it is 2, record $-1$ and carry 1 into the next digit.

   5 = 9 - 3 - 1     = (1, -1, -1)
  -5 = -9 + 3 + 1    = (-1, 1, 1)
   7 = 9 - 3 + 1     = (1, -1, 1)

The classic application: the balance scale

With weights $1,3,9,27,\dots$ and a two-pan balance, you can weigh any integer mass.

Because each weight can go on the empty pan (coefficient $+1$), on the object’s pan ($-1$), or be unused ($0$) — exactly the three balanced-ternary digits. With weights up to $3^k$ you can measure every mass from 1 to $\frac{3^{k+1}-1}{2}$.

This is Bachet’s weight problem, and it is the canonical reason the representation is worth knowing.

Properties

Property
Representation is unique	for every integer, positive or negative
Negation = flip every digit’s sign	no two’s-complement asymmetry
No separate sign bit	the leading digit carries it
Rounding = truncation	truncating always gives the nearest value
Range with $k$ digits	$\left[-\frac{3^k-1}{2},\frac{3^k-1}{2}\right]$ — symmetric
Digit count for $n$	$\approx {\log }_3(2|n|)$

The symmetric range and free negation are why balanced ternary is occasionally called “the most elegant number system”. The Soviet Setun computer (1958) used it.

Where it appears in problems

Problem	Why balanced ternary
”Weigh any mass with weights $3^k$“	the defining example
”Represent $n$ as $\pm 3^a\pm 3^b\pm \dots$ with distinct exponents”	exactly the representation
”Can $n$ be made from powers of 3, each used at most once, with $\pm$?“	always yes, and uniquely
Games where each move is $\pm 3^k$	state = balanced ternary digits
Ternary search trees / three-way partitioning	the three-outcome analogy
”Minimum number of powers of 3 summing to $n$ with signs”	popcount of the non-zero digits

Generalisation: non-adjacent form (NAF)

The base-2 analogue uses digits $\{-1,0,1\}$ with the rule that no two adjacent digits are non-zero. Every integer has a unique NAF, and it has the minimum possible number of non-zero digits — on average $n/3$ instead of $n/2$.

vector<int> naf(long long n) {
    vector<int> d;
    while (n) {
        if (n & 1) { int z = 2 - (int)(n % 4); d.push_back(z); n -= z; }
        else d.push_back(0);
        n >>= 1;
    }
    return d;
}

This makes modular exponentiation and elliptic curve scalar multiplication about 11% faster, because each non-zero digit costs a multiplication and NAF has fewer of them. It is the standard optimisation in cryptographic implementations.

Related representations

System	Digits	Note
Binary	$\{0,1\}$	the default
Balanced ternary	$\{-1,0,1\}$ base 3	symmetric, free negation
NAF	$\{-1,0,1\}$ base 2	minimal weight
Zeckendorf	$\{0,1\}$, Fibonacci base	no two adjacent 1s
Factorial base	digit $i$ in $[0,i]$	permutation ranking
Gray code	$\{0,1\}$	consecutive values differ in one bit
Negabinary	base $-2$	represents negatives without a sign bit

Factorial base is worth knowing alongside: it is how you convert between a permutation and its lexicographic rank, via the Lehmer code.

See also: Gray Code · Binary Exponentiation · General Number Theory