Binary expansion (source code)

= Binary expansion

Every <real number> $x\in[0,1]$ has a binary expansion
$$
x=\sum_{j=1}^{\infty}b_j2^{-j},\qquad b_j\in\{0,1\}.
$$
For $0\leq x<1$, construct it by repeated doubling. Set $r_0=x$, then $b_j=\lfloor2r_{j-1}\rfloor$ and $r_j=2r_{j-1}-b_j$, using the <floor function>. Each remainder stays in $[0,1)$, and induction gives
$$
x=\sum_{j=1}^n b_j2^{-j}+2^{-n}r_n.
$$
The remaining error is less than $2^{-n}$, so the finite <partial sums> converge to $x$. For $x=1$, choose every <binary digit> equal to one and use the <geometric series>.

\Image[/binary-expansion-nested-intervals.png]
{title=Successive <binary digits> refine an <interval> around $2/3$}
{description=Each blue <interval> runs from the $n$th <partial sum> $s_n$ to $s_n+2^{-n}$. Filled left endpoints are included and open right endpoints are excluded. The red line marks $x=2/3=0.101010\ldots_2$; the labels show its successive binary prefixes. Each new digit halves the remaining interval's length.}

An expansion need not be unique: $0.1_2=0.01111\ldots_2=1/2$. For $0<x<1$, this ambiguity occurs precisely at the <dyadic rationals>, through a terminating expansion and an alternative ending in ones. At the endpoints, the displayed purely fractional form uses all zeros for zero and all ones for one. A general nonnegative <real number> is represented by adding the finite <binary representation> of its <floor> to an expansion of its <fractional part>; a negative <real number> is handled by a separate sign. In that broader notation, $1.0_2=0.1111\ldots_2$ too.