Binary and $m$ -ary notation

Each natural number is most commonly written in decimal form (or base $10$ ),

$$a=a_k10^k+...a_1 10+a_0,$$

where $0\leq a_i\leq 9$ are the digits. (Without loss of generality we may assume that the leading digit $a_k$ is non-zero.) This representation is unique. (In spite of the fact that the decimal representation of a real number is not unique - $1.0=.9999....$ .) Similarly, each natural number can be written (uniqely) in a binary expansion (or base $2$ ),

$$a=a_k2^k+...+a_1 2+a_0,$$

where $0\leq a_i\leq 1$ are the bits. The binary representation of $a$ is written as $a\sim a_k...a_1a_0$ . Clearly, $a$ is even if and only if $a_0=0$ . To find the binary expansion of a natural number, perform the following steps.

(1)

Find the ``leading bit'' $a_k$ by determining the largest power of $2$ less than or equal to $a$ . Call this power $k$ and let $a_k=1$ .

(2)

Subtract this power from $a$ and replace $a$ by this difference.

(3)

If the result is non-zero, go to step 1; otherwise, stop.

This determines all the non-zero bits in the binary representation of $a$ . The other bits are 0 .

Example 1.3.1   Find the binary representation of $130$ . The largest power of $2$ less than or equal to $130$ is $128=2^7$ , so $a_7=1$ . The largest power of $2$ less than or equal to $2=130-128$ is $2=2^1$ , so $a_1=1$ . The other bits are zero: $a_6=a_5=a_4=a_3=a_2=a_0=0$ , so

$$130=128+2\sim 10000010.$$

More generally, let us fix an integer $m>1$ . Each natural number can be written in an $m$ -ary expansion

$$a=a_km^k+...+a_1 m+a_0,$$

where $0\leq a_i\leq m-1$ are the $m$ -ary digits. Again, the $m$ -ary representation of $a$ is written as $a\sim a_k...a_1a_0$ . Clearly, $m\vert a$ if and only if $a_0=0$ . To find the $m$ -ary expansion of a natural number, perform the following steps.

(1)

Find $a_k$ by determining the largest power of $m$ less than or equal to $a$ . Call this power $k$ .

(2)

Find the largest positive integer multiple of this power which is less than or equal to $a$ . This multiple will be the $k$ -th digit $a_k$ .

(3)

Subtract $a_km^k$ from $a$ and replace $a$ by this difference.

(4)

If the result is non-zero, go to step 1; otherwise, stop.

Example 1.3.2   Find the $3$ -ary representation of $211$ . The largest power of $3$ less than or equal to $211$ is $81=3^4$ , and $211>2\cdot 81=162$ so $a_4=2$ . The largest power of $3$ less than or equal to $49=211-162$ is $27=3^3$ , and $49<2\cdot 27$ so $a_3=1$ . The largest power of $3$ less than or equal to $22=49-27$ is $9=3^2$ , and $22>2\cdot 9$ so $a_2=2$ . The largest power of $3$ less than or equal to $4=22-18$ is $3=3^1$ , and $4<2\cdot 3$ so $a_1=1$ . The last ``bit'' is 1: $a_4=2,a_3=1,a_2=2,a_1=1,a_0=1$ , so

$$211=2\cdot 3^4+1\cdot 3^3+2\cdot 3^2+1\cdot 3+1\sim 21211.$$

Example 1.3.3   Convert $100101$ from binary to $5$ -ary. In decimal (or ``$10$ -ary''), $100101$ is

$$1\cdot 2^5+0\cdot 2^4+0\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0=32+4+1=37.$$

In $5$ -ary,

$$37=1\cdot 5^2+2\cdot 5^1+2\cdot 5^0\sim 122.$$