Converting numbers to different bases

Question

I am converting numbers between different bases without issues, but I'm struggling to understand the why the method I'm using works.

If I convert $A5$ (base 16) to base 8, I would do the following:

Turn $A5$ into binary (4 bits)

$A = 1010$

$5 = 0101$

$10100101$ (split into three bits) $= 010$ $100$ $101$

$010$ = 2

$100$ = 4

$101$ = 5

$A5$ (base 16) $= 245$ (base 8)

I know the answer is correct, but I don't understand why the binary is split into $X$ bits depending on the base, and how the value $X$ is chosen. If it's base 4, for example, how many bits should the binary be separated into when converting?

Answer 1

This approach only works for bases that are powers of $2$. So, for base $2^k$ you convert to binary by concatenating strings of $k$ bits, one for each base-$2^k$ digit. In the other direction, you convert from base $2$ to base $2^k$ by dividing the binary digits in groups of $k$ (and possibly padding with leading $0$s to get a number of binary digits that is a multiple of $k$).

The explanation is simple once you think that the number represented by a binary numeral $b_{n-1}\cdots b_1 b_0$ is

$$ \sum_{0 \leq i <n} b_i 2^i \enspace. $$

If, without loss of generality because of the padding, we assume that $n$ is a multiple of $k$, we can rewrite the summation as

$$ \sum_{0 \leq i < n/k} \Big( \sum_{0 \leq j < k} b_{ik+j} 2^j \Big) (2^k)^i \enspace. $$

Each summation in parentheses is a base-$2^k$ digit.

Answer 2

This approach only works when the base is a power of $2$. In that case you use $n$ bits when the base is $2^n$. In base $16=2^4$ you use four bits. There are $2^n$ binary strings of length $n$. In base $4=2^2$ you use $2$ bits.

Answer 3

This works because Base $b$ is equal base $a$ to a power. i.e. converting from base $a$ to base $a^k$.

This will not work for any other type conversion.

Here is why it works:

In base $a$ an $n + 1 $ digit number $N = \sum_{i=0}^n d_i*a^i$. Okay, let $n = q*k + r$ where $0 \le r < k$. (This is just the division algorithm.)

For simplicity sake lets define $d_{t} = 0$ for $t > n$.

So we can so $N = \sum_{i=0}^{(q+1)*k - 1} d_i*a^i$. (It's just that the $n+1 = q*k + r + 1$ to $q*k + (k-1)=(q+1)*k -1$ digits are all $0$s.)

So $N = \sum_{i=0}^{qk+r} d_i*a^i = \sum_{j=0}^{q} [d_{k*j}a^{k*j} + d_{k*j + 1}a^{k*j + 1} + ..... d_{k*j + (k-1)}*a^{k*j + (k-1)}]$

$= \sum_{j=0}^{q} (a^k)^j*[d_{k*j}a^{0} + d_{k*j + 1}a^{ 1} + ..... d_{k*j + (k-1)}*a^{k-1}]$

Now $0 \le [d_{k*j}a^{0} + d_{k*j + 1}a^{ 1} + ..... d_{k*j + (k-1)}*a^{k-1}]< a^k = b$.

So let $c_j = [d_{k*j}a^{0} + d_{k*j + 1}a^{ 1} + ..... d_{k*j + (k-1)}*a^{k-1}]$ be a base $b$ digit.

So $N = \sum_{j=0}^{q} (a^k)^j*[d_{k*j}a^{0} + d_{k*j + 1}a^{ 1} + ..... d_{k*j + (k-1)}*a^{k-1}]$

$= \sum_{j=0}^{q} b^j c_j$.

is a $q+1$ digit base $b$ number.