Positional Numeral System

Positional numeral system, also known as carry system, base system, positional notation, place-value notation, or positional numeral system, is a numeral system that can represent all natural numbers using a finite set of symbols. The number of symbols available in a positional system is called its radix or base. A positional system with radix $n$ is called the $n$-ary system ($n>1$); for example, the decimal system we use most often generally uses only the ten symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 for notation. Carrying is the operation of “when a digit in some position reaches the base, set it to 0 and increment the digit in the next higher position.”

In general, we write a number in base $n$ as $(a_k\cdots a_1a_0)_n$, $(a_k\cdots a_1a_0)_{(n)}$, ${a_k\cdots a_1a_0}_{(n)}$, ${a_k\cdots a_1a_0}_{n}$, and so on. If the base is implicit from the context, the subscript may be omitted. Note that $a_k\cdots a_1a_0$ here is not the product of $k+1$ numbers, but a sequence.

For a base-$k$ number $a_n\cdots a_1a_0$, its value is $a_nk^n+\cdots+a_1k^1+a_0k^0=\sum_{i=0}^n a_ik^i$; for a number $m$, suppose its representation in base $k$ is $a_n\cdots a_1a_0$. Then:

where $f(x)=\lfloor x\rfloor$.

The length of the representation of $n$ in base $k$ is $\lceil\log_k (n+1)\rceil$.

We generally use a decimal point “$.$” to represent fractions¹, a minus sign “$-$” to represent negative numbers, and an overline over the final part of a decimal to represent an infinite repeating fraction. For readability, we may insert separators between groups of digits, such as spaces, $,$, or '; for example, $12~345$ represents $12345$.

The positional systems commonly used in computers include binary, octal, and hexadecimal.

Conversion between positional systems

Decimal to other bases

We use binary as an example here; the principle is similar for other bases.

For the integer part, repeatedly divide the decimal number by $2$ until the quotient is $0$, then take the digits of all remainders from bottom to top; these are the digits of the binary integer part. For the fractional part, multiply it by $2$, take the integer part of the result, and then repeat the process with the fractional part obtained from the calculation until the fractional part is all $0$. Finally, take the integer parts obtained in each calculation from top to bottom; these are the digits of the binary fractional part.

#include <algorithm>
#include <string>

// only non-negative
// 2 <= base && base <= 36
std::string from_dec(int x, int base) {
  if (x == 0) return "0";
  std::string res;
  while (x) {
    int r = x % base;
    x /= base;

    // Method 1
    res.push_back(r < 10 ? '0' + r : 'A' + r - 10);
    // Method 2
    // const static std::string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    // res.push_back(digits[r]);
  }
  std::reverse(res.begin(), res.end());
  return res;
}

Other bases to decimal

Again, we use binary as an example. To convert a binary number to a decimal number, simply multiply the value of each digit by $2^i$, where $i$ is the position of the current digit and the units digit has position $0$.

#include <cctype>
#include <string>

// only non-negative
// 2 <= base && base <= 36
int to_dec(std::string const& s, int base) {
  int res = 0;
  for (char c : s) {
    res *= base;
    if (isdigit(c))
      res += c - '0';
    else if (isupper(c))
      res += c - 'A' + 10;
    else if (islower(c))
      res += c - 'a' + 10;
  }
  return res;
}

Conversion among binary, octal, and hexadecimal

One octal digit can be represented by 3 binary digits (because $2^3 = 8$), and one hexadecimal digit can be represented by 4 binary digits ($2^4 = 16$); the converse follows similarly.

Method of complements

See also: Ones' and two's complements

The method of complements is a method of representing negative numbers with positive numbers, so that subtraction can be computed using the same algorithms, circuits, or mechanical structures as addition with positive numbers. The method of complements is widely used in the design of calculators and computers to simplify their structure.

For an $n$-digit base-$b$ number $a$, its radix complement (also called the complement to $b$) is $b^n-a$, while its diminished radix complement (also called the complement to $b-1$, or simply the diminished complement) is $b^n-1-a$. In binary, the radix complement is called the complement to $2$ (two's complement), also known as two's complement representation; the diminished radix complement is called the complement to $1$ (ones' complement), also known as one's complement representation; in decimal, the radix complement is also called the complement to $10$ (ten's complement), and the diminished radix complement is also called the complement to $9$ (nine's complement); other bases follow the same pattern.

For $n$-digit base-$b$ numbers $x,y$, when computing $x-y$, we have the following methods (if the result exceeds $n$ digits, discard the higher digits):

1. Consider the diminished complement $x'=b^n-1-x$ of $x$, and compute $x'+y=b^n-1-x+y$; the diminished complement of this result is the answer.
2. Consider the diminished complement $y'=b^n-1-y$ of $y$, and compute $x+y'=b^n-1+x-y$; simply add one to obtain the answer.
3. Consider the radix complement $x'=b^n-x$ of $x$, and compute $x'+y=b^n-x+y$; the radix complement of this result is the answer.
4. Consider the radix complement $y'=b^n-y$ of $y$, and compute $x+y'=b^n+x-y$; this is the answer.

In addition, for a number in base $k$, let $d=k-1$. Then $\cdots dd=:\overline{d}=\sum_{i=0}^{\infty} dk^i=-1$. Therefore, for an $n$-digit number $x$, if its radix-complement representation in base $k$ is $a_{n-1}\cdots a_1a_0$, then $\overline{d}a_{n-1}\cdots a_1a_0$ is $\sum_{i=0}^{n-1}a_ik^i+\sum_{i=n}^{\infty} dk^i=k^n-x+(-k^n)=-x$. This idea of “numbers with infinitely many digits” can be generalized to $p$-adic numbers ($p$-adic number).

Furthermore, we have an interesting theorem about complements and infinite repeating decimals:

Generalized positional systems

In a standard positional system, the base $b$ is always a fixed positive number, and each digit is selected from $b$ different symbols to represent a nonnegative number (disregarding the decimal point and minus sign). In fact, many other numeral and positional systems have similar characteristics but do not fully satisfy the definition of a positional system. We call such systems generalized positional systems or non-standard positional numeral systems. Several common generalized positional systems are introduced below.

Bijective numeral systems

Standard positional systems cannot establish a bijection with the numbers they represent: for example, $1$, $01$, and $001$ represent the same number³, whereas a bijective numeral system can establish a bijection with the numbers it represents.

Bijective base $k$ ($k\geq 1$) uses the set $\{1,2,\dots,k\}$ to represent each number uniquely, according to the following rules:

1. The empty string represents $0$;
2. A nonempty string $a_n\cdots a_1a_0$ represents the number $a_nk^n+\cdots+a_1k^1+a_0k^0=\sum_{i=0}^n a_ik^i$.

For a positive number $m$, suppose its representation in bijective base $k$ is $a_n\cdots a_1a_0$. Then:

where $f(x)=\lceil x\rceil-1$.

For example, Microsoft Excel's column labels use bijective base $26$.

In the bijective numeral system, we have the unary numeral system, in which a nonempty string consists only of $1$s, and the length of the string is the number it represents.

As in the discussion of the method of complements, in bijective base $k$ with $k>1$, let $d=k-1$. Then $\cdots dd=:\overline{d}=\sum_{i=0}^{\infty} dk^i=-1$, and therefore $\overline{d}k=0$. Thus, if the representation of $x$ in bijective base $k$ is $a_{n-1}\cdots a_1a_0$, then $\overline{d}ka_{n-1}\cdots a_1a_0$ is $-x$.

Here are some properties of bijective base-$k$ numbers:

• There are $k^l$ numbers of length $l\geq 0$.
• When $k\geq 2$, the length of the representation of $n$ in bijective base $k$ is $\lfloor\log_k (n+1)(k-1)\rfloor$.
• When $k\geq 2$, if the representation of a number $n$ in base $k$ contains no $0$, then its representation in base $k$ is the same as its representation in bijective base $k$.

The code for converting bijective base $k$ to decimal is the same as the code for converting base $k$ to decimal. Below is a reference implementation for converting decimal to bijective base $k$.

#include <algorithm>
#include <string>

// only non-negative
// 1 <= base && base < 36
std::string from_dec_bi(int x, int base) {
  std::string res;
  while (x > 0) {
    int q = (x + base - 1) / base - 1, r = x - q * base;
    x = q;

    // Method 1
    res.push_back(r < 10 ? '0' + r : 'A' + r - 10);
    // Method 2
    // const static std::string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    // res.push_back(digits[r]);
  }
  std::reverse(res.begin(), res.end());
  return res;
}

Signed-digit bases

Some positional systems allow negative numbers to occur as digits, such as balanced ternary.

Gray code

Main article: Gray code

Gray code is also called cyclic binary code or reflected binary code (reflected binary code, RBC). It is a special binary numeral system, commonly used for data checking.

Non-positive bases

We know that for a base-$k$ number $a_n\cdots a_1a_0$, its value is $\sum_{i=0}^n a_ik^i$. With a slight modification, we can define a base-$-k$ number ${a_n\cdots a_1a_0}_{(-k)}$ to represent $\sum_{i=0}^n a_i(-k)^i$, where $a_n,\dots,a_1,a_0\in \{0,1,\dots,k-1\}$. For example, $12345_{(-10)}=8265_{(10)}$. This positional system is called a negative-base system.

Similarly, we can define a complex-base system, such as a $2\mathrm{i}$ base system (quater-imaginary base, quater-imaginary numeral system). We can also define a non-integer base of numeration for the $\beta$-expansion ($\beta$-expansion) of real numbers.

Mixed-radix systems

In a standard positional system, the base corresponding to every digit is fixed, while a mixed-radix system allows each digit to correspond to a different base. The most common application of mixed-radix systems is timekeeping: hours use base $24$, while minutes and seconds use base $60$.

The number represented by $a_n\cdots a_1a_0$ in base $b$ is $\sum_{i=0}^n a_ib^i$, while in a mixed-radix system it is $\sum_{i=0}^n a_i\prod_{j=0}^{i-1}b_j$, where $b_j$ is the base corresponding to $a_j$.

In algorithmic competitions, the most common mixed-radix system is the factorial number system, whose numbers can be written as ${a_n\cdots a_1a_0}_{~!}$ and whose value is $\sum_{i=0}^na_i i!$⁴. For applications of the factorial number system in algorithmic competitions, see Lehmer code/Cantor expansion.

#include <algorithm>
#include <string>

// only non-negative
std::string from_dec_factorial(int x) {
  if (x == 0) return "0";
  std::string res;
  int base = 1;
  while (x) {
    int r = x % base;
    x /= base++;

    // Method 1
    res.push_back(r < 10 ? '0' + r : 'A' + r - 10);
    // Method 2
    // const static std::string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    // res.push_back(digits[r]);
  }
  std::reverse(res.begin(), res.end());
  return res;
}

#include <cctype>
#include <string>

// only non-negative
int to_dec_factorial(std::string const& s) {
  int res = 0, base = s.size();
  for (char c : s) {
    res *= base--;
    if (isdigit(c))
      res += c - '0';
    else if (isupper(c))
      res += c - 'A' + 10;
    else if (islower(c))
      res += c - 'a' + 10;
  }
  return res;
}

Implementation in C++

For nonnegative numbers, C++ uses <前缀><数位><后缀> to represent an integer literal, where <数位> and <后缀> may both be empty. <后缀> indicates the type of the literal: for example, u or U indicates that the literal is unsigned, while l or L indicates that it is long, and so on. For <前缀>:

• When <前缀> is 0x or 0X, it denotes a hexadecimal literal, and the characters in <数位> can only be selected from 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, A, b, B, c, C, d, D, e, E, f, F. For example, 0x1234ABCD is $\text{1234ABCD}_{(16)}=305~441~741$;
• When <前缀> is 0, it denotes an octal literal, and the characters in <数位> can only be selected from 0, 1, 2, 3, 4, 5, 6, 7. For example, 01234567 is $1234567_{(8)}=342391$; ⁵
• When <前缀> is 1, 2, 3, 4, 5, 6, 7, 8, or 9, it denotes a decimal literal, and the characters in <数位> can only be selected from 0, 1, 2, 3, 4, 5, 6, 7, 8, 9;
• Since C++14, when <前缀> is 0b or 0B, it denotes a binary literal, and the characters in <数位> can only be selected from 0, 1. For example, 0b11001010 is $11001010_{(2)}=202$.

References and notes

• Positional notation - Wikipedia
• Method of complements - Wikipedia
• Non-standard positional numeral systems - Wikipedia
• Bijective numeration - Wikipedia
• Midy's theorem - Wikipedia
• N3472 - Binary Literals in the C++ Core Language