Why does the method of converting from decimal binary by taking remainder work?

Question

For example, you want to 100 decimal to a binary number in zeroes and ones. You keep divide 100 by 2 until you have 0 left. And the remainders will be a binary number. 1100100. The first 1 is the remainder you get by dividing 1 by 2. The last 0 is the remainder you get when you first divide 100 by 2.

The easiest-to-understand way of converting from decimal to binary is, first find the largest power of 2 that is smaller than 100. And substract that power of 2 from 100. And find the largest power of two that is smaller than that difference we found. Repeat this over and over until you get to 1, which is the two to the zero power.

Answer 1

The binary expression of the number $n$ is given by $$ n=a_0+a_1\cdot2+a_2\cdot 2^2+\dots+a_k\cdot 2^k $$ where $a_i$ is $0$ or $1$ and $2^k$ is the largest power of $2$ less than or equal to $n$ (and $a_k=1$).

Now, observe that $$ n=a_0+2(a_1+a_2\cdot2+\dots+a_k\cdot2^{k-1}) $$ and therefore, when you divide $n$ by $2$, the remainder is $a_0$ and the quotient is $$ n_1=a_1+a_2\cdot2+\dots+a_k\cdot 2^{k-1} $$ Similarly, when you divide $n_1$ by $2$, the remainder is $a_1$ and the quotient is $$ n_2=a_2+\dots+a_k\cdot 2^{k-2} $$ Continuing in this way, we arrive finally at $$ n_k=a_k $$ Thus the procedure of successively dividing by $2$ and collecting the remainders produces the digits in the binary representation of $n$, starting from the less significant digit. Note that we don't need to know $k$ in advance: the algorithm stops when the last quotient is $0$.

Finding the largest power of $2$ less than or equal to $n$ yields the most significant digit. It's an alternative procedure, but it requires to know the powers of $2$, which is not needed with the algorithm of successive divisions.

So successive divisions provide a more efficient algorithm.

By the way, the algorithm is the same for every radix. The alternative method for radix $b$ requires a table of the powers of $b$ together with their multiples by $2$, $3$ and so on up to $b-1$.

Answer 2

More exactly, the highest power (of remaining) give you the position of a next 1 in that binary form. For example : $$ 100 = 2^6+R $$ where R is a rest. So our first 1 is on position 7 counting from right : $$ 1xxxxxx $$ A x can be 0 or 1. What left over : $$ R = 100-2^6=36 $$ From this we get next 1 position in binary form : $$ 36 = 2^5+R_2 $$ So we get now $$11xxxxx$$ We rest : $$ R_2=36-2^5=4 $$ Get a power of 4 : $$ 4 = 2^2+0 $$ We already put a 1 in position 7 (from right) and position 6 (always one more if we count that first position is for $2^0$. Now we get that power is 2, so we need to put a 1 in third position. What is with fifth and fourth position ? This will be filled with zeros : $$ 11001xx $$ Remainer is 0, so last binary numbers are also 0 : $$ 1100100 $$ This will help you ?
Greatings, Daniel

Answer 3

You can understand how it works by thinking of how you could find the decimal digits of a number $N$: the rightmost digit is just the remainder of the division $N/10$. Now repeat the same thing with the integer quotient of $N/10$ and so on, until you get all the digits. That works in any base.