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

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.

• egreg’s answer, below, gives you the mathematical explanation. You can visualize what’s going on by observing that division by 2 corresponds to a right-shift in binary. The bit that gets shifted “off the end” is the remainder. Successive division by 2 thus spits out the sequence of bits in the binary representation of the number, starting with the least-significant. – amd Oct 8 '17 at 22:10

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$).

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}$$ 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 algoritm 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 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$.

• This is kinda abstract. But it works. – most venerable sir Oct 9 '17 at 22:59
• Why is the remainder of the first division $a_0$? This is one of the most fundamental flaws with mathematicians. They're great at what they do but sometimes can't explain things very well to others. What makes sense in your mind may not make sense in others' minds. I for the life of me can't figure out why $2^-1$ times $a_0$ would make $a_0$ a remainder. – AleksandrH Jul 4 '18 at 13:59
• @AleksandrH $n=a_0+2(a_1+a_2\cdot 2+\dots+a_k\cdot2^{k-1})$ seems like an expression of the form $n=2q+r$ with $0\le r<2$. – egreg Jul 4 '18 at 14:02
• @egreg Oohhhh, okay, that's a much clearer explanation. – AleksandrH Jul 4 '18 at 14:35

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

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.