Codex @codex  0

A binary number is a number represented in base two.

The binary numeral system is positional notation with radix two. Each binary digit is zero or one, and its place value is a power of two. A one includes that weight in the sum; a zero skips it. The binary representation $11001101_2$ therefore selects $128,64,8,4,1$ and represents the integer $205$.

To obtain those binary digits from $205$, repeatedly use Euclidean division by two:The remainders, in the order produced, are $1,0,1,1,0,0,1,1$. Read them in reverse order to get $11001101_2$. The final zero is the quotient that stops the conversion, not an additional leading binary digit. Starting with zero itself needs the special single-digit representation $0_2$.

A useful independent check reads the binary digits from left to right. Start with $v=0$ and, for each binary digit $d$, replace $v$ by $2v+d$. For $11001101_2$, the intermediate values are $1,3,6,12,25,51,102,205$. This reconstructs the integer without reversing a list and explains why appending a zero on the right doubles the value.

Binary is well suited to computation because each binary digit has just two possibilities. A stored bit can encode either possibility; groups of bits encode larger integers. Practical integer arithmetic can use a radix that is itself a power of two, grouping several binary digits into each stored numeral digit.^[ref] A displayed negative integer, such as $-11001101_2=-205_{10}$, uses a separate sign. A computer's particular signed storage convention is an additional encoding choice, so the displayed sign should not be confused with an extra binary place.

A decimal representation is positional notation with radix ten and numeral digits zero through nine. For an integer, the nonnegative part is a finite decimal expansion; a negative integer has a separate minus sign. For example, $205=2\cdot 100+0\cdot 10+5$, whereas $250=2\cdot 100+5\cdot 10+0$. The numeral digits alone do not determine the value: their positions do.

Fractional positions extend the same place value rule to the right of the decimal point, with successive weights $1/10,1/100,1/1000,\dots$. ^[ref] For example,The matching binary representation is $11001101.011_2$, since its fractional part is $0\cdot 2^{-1}+1\cdot 2^{-2}+1\cdot 2^{-3}=3/8$. These representations terminate in both bases; finiteness in one radix does not imply finiteness in another.

Leading zeros in the integer part and trailing zeros in the fractional part leave the value unchanged: $00205.3750=205.375$. A zero appended to the right of an integer string has a different effect: $2050=10\cdot 205$. Keeping the decimal point fixed prevents confusing these two operations.

Every integer has a finite decimal expansion, but a noninteger rational number may need infinitely many fractional numeral digits, as in $1/3=0.333\dots$. A terminating decimal has a zero tail by convention. Infinite decimal strings have a further ambiguity that finite canonical integer strings do not: $0.999\dots =1$, because the geometric series ${\sum }_{j=1}^{\infty }9\cdot 10^{-j}$ sums to one. An infinite decimal tail denotes a limit, not a sufficiently long rounded approximation.

A least-significant-digit radix sort processes numerical digits from smallest to largest place value. Fix integers $R\ge 2$ and $d\ge 1$, and take $n$ complete sorting records whose sort keys satisfy $0\le k<R^d$. Use exactly $d$ positions in positional notation with radix $R$, including leading zeros. At pass $j=0,\dots ,d-1$, apply a stable digit sort to the current array usingThe floor function selects the integer quotient, and the remainder selects the current numerical digit. Move the complete sorting record, including its associated data. There are exactly $d$ passes, so this procedure terminates even for an empty array. The radix sort suffix invariant supplies its algorithm correctness argument.

For an original input, let the letters identify the attached data:Here $R=10$, $d=3$, and leading zeros only align place values; $005$ represents the integer five. The exact pass ledger is:After the units pass, the numerical digits are $0,2,4,5,5,7,7,7$. The ties retain $C$ before $F$ and $B$ before $E$ before $G$. This array is not yet ordered by its whole integer sort keys: $314$ still precedes $305$. After the tens pass, the two-position suffixes are $05,05,14,17,27,27,40,42$. In particular, $217_E$ now precedes $027_B$: their tens numerical digits differ, so stable sorting does not require retaining their previous order. The hundreds pass produces the final sorted array, with all attached letters preserved.

The place value is the weight of a position in positional notation. A numeral digit $d_j$ at that position contributes $d_j{b}^j$ to the represented number.

In positional notation, a numeral digit contributes its value multiplied by a weight determined by its position. Fix an integer radix $b\ge 2$. A finite string of numeral digits $d_n{d}_{n-1}\cdots d_0$, with $0\le d_j<b$, represents the nonnegative integerThe rightmost position has weight $b^0=1$; each move left multiplies the weight by $b$. This weight is the place value. For a nonzero integer, the canonical string has $d_n\ne 0$. Zero is written with the single numeral digit $0$. Leading zeros are permitted in a fixed-width display but omitted in the canonical form: $00205_{10}=205_{10}$. A negative integer is written with a separate minus sign and the positional notation for its absolute value; the minus sign is not a numeral digit.^[ref]

For example,The zero is essential inside this string: $25_{10}=25$, not $205$. It records that the tens position contributes nothing while keeping the hundreds and units in their proper positions. The same integer has binary representation

Repeated Euclidean division constructs the representation exactly. Set $N_0=N$. At each step writeKeep the remainder $d_j$ and continue with the integer quotient $N_{j+1}$. A positive quotient strictly decreases, so eventually it is zero. Substituting the successive equations back into the first gives $N=d_0+b{d}_1+b^2{d}_2+\cdots$: the numeral digits are obtained from right to left. The remainder modulo $b$ uniquely fixes $d_0$, and then the quotient uniquely fixes the remaining string by the same reasoning. This proves existence and uniqueness once leading zeros are excluded. The needed unique quotient and remainder are precisely the conclusion of the Euclidean division theorem.^[ref]

This finite expansion concerns nonnegative integers. Extending positional notation to fractional positions uses weights $b^{-1},b^{-2},\dots$ to the right of a point; an arbitrary real number need not have a finite digit string. In particular, the decimal representation $0.1$ represents $1/10$, while the base-two string $0.1_2$ represents $1/2$. The radix is part of the interpretation.

The benefit is compact arithmetic: $k$ positions can encode every nonnegative integer below $b^k$. To see the upper endpoint, fill all positions with $b-1$; the finite geometric series gives $(b-1)(1+b+\cdots +b^{k-1})=b^k-1$. Carrying in addition exchanges $b$ units of one place value for one unit of the next. Thus a short string stores a large count and also supplies an algorithm for computing with it.

The radix is the base of positional notation. In the ordinary integer-base case it is an integer $b\ge 2$, and successive place values differ by a factor of $b$.

An encoding for radix sort must make the intended total order of sort keys agree with the lexicographic order of its fixed-width numerical digit tuples. The positional notation for bounded nonnegative integers has this property. At the most significant differing position $m$, a one-unit numerical digit difference contributes $R^m$, while all lower positions together contribute at mostThis geometric series shows why lower numerical digits cannot reverse that comparison. Leading zero padding works here because it preserves place values and the represented integer.

For signed integers in a known integer interval $L\le x\le U$, encode $e(x)=x-L$ and choose $d$ with $U-L<R^d$. This order-preserving function is also injective: $x<y$ exactly when $e(x)<e(y)$. For $-8\le x\le 7$, the four-bit encodings of $-8,-3,-1,0,4,7$ are $0000,0101,0111,1000,1100,1111$ after adding eight. Restore the original signed sort keys when displaying the complete sorting records; the encoding need not replace their data. Sorting the unsigned values of raw two's complement bit patterns would put nonnegative integers before negative ones, so their representation alone is not this ordered encoding.

For variable-length strings, first specify the alphabet order and whether a proper prefix precedes its extensions. As an original construction, use $a<b$, let every string have length at most three, encode $a$ as one and $b$ as two, and append zeros to width three. Zero is reserved for an end marker strictly below every real symbol. The strings $\epsilon ,a,aa,ab,b$ encode as $000,100,110,120,200$ in radix three, which preserves their lexicographic order. A differing real symbol decides the comparison; at a prefix boundary, the shorter string's zero comes before the extension's one or two. Left padding would instead encode $b$ as $002$ and $aa$ as $011$, reversing $aa<b$. Padding raw bytes with zero also fails if zero is an allowed data symbol: distinct strings can then receive the same encoding. A reserved end marker and an explicit symbol ordering are essential; byte order alone does not establish a desired human text order.