Previous | ToC | Next Labs: Cryptography. Part 1. Math Alive

## Conversion from Decimals to Binary

There are two methods of converting decimals to binary. Here we present both methods using the number 85 as an example.

First method. We are trying to represent the number 85 as the sum of powers of two starting from the largest. Find the largest power of 2 which is not more than 85. It is 64 = 26. Subtract it: 85 - 26 = 21. The result will always be less than the power of two that was subtracted (can you figure out why?). Now we need to represent 21 as the sum of powers of 2. Continue as before: the biggest power of two which is not more then 21 is 16 = 24. Subtract it: 21 - 24 = 5. Now we need to represent 5 as the sum of powers of 2. Continue as before: the largest power of two which is not more then 5 is 4 = 22. Subtract it: 5 - 22 = 1. We can represent 1 as 20. We got that 85 = 26 + 24 + 22 + 20. This is the same as:
85 = 1 * 26 + 0 * 25 + 1 * 24 + 0 * 23 + 1 * 22 + 0 * 21 + 1 * 20.
The binary representation of 85 is given by the coefficients in this representation listed one after another, starting with the highest power of 2: 1010101.

Second method. This method is based on two observations.
First observation: the last digit in the binary representation is always the remainder of the number when divided by two. That is, it is 1 if the number is odd, and 0 if it is even.
Second observation: if we erase the last digit of a binary number, then we get a new binary number which is equal to half the original number, with the fraction of 1/2 dropped if the original number was odd.
For example, consider the number n whose binary representation is abcd is equal to a * 23 + b * 22 + c * 21 + d * 20.
Then note that n = 2 * (a * 22 + b * 21 + c * 20) + d. So n is even if d=0 and odd if d=1 (first observation). Also note that if we divide n by two and drop any fraction of 1/2 (if d is odd), then we get a * 22 + b * 21 + c * 20, which has binary representation abc, which is what you get if you erase the last binary digit of n (second observation).
Although we only proved our observations with 4-digit binary numbers, the same argument works no matter how many digits we have.

The number 85 is odd. Hence, the last digit is 1. Subtract 1, we get 84. Then dividing 84 by 2 we get 42. Binary representation of 42 will get us all other digits in front of the last.
So [binary represenation of 85]=[binary representation of 42]1.
The number 42 is even, hence its last binary digit is 0. Dividing 42 by 2 we get 21.
So [binary represenation of 85]=[binary representation of 21]01.
21's last binary digit is 1 (as it is odd). Subtract 1 and divide by two again: we get 10.
So [binary represenation of 85]=[binary representation of 10]101.
10's last binary digit is 0. 10/2 = 5.
So [binary represenation of 85]=[binary representation of 5]0101.
5's last binary digit is 1. Then 4/2 = 2.
So [binary represenation of 85]=[binary representation of 2]10101.
2's last binary digit is 0. Dividing 2 by 2, we get 1.
So [binary represenation of 85]=[binary representation of 1]010101.
Now the binary digit 1 represents the number 1.
So the binary represenation of 85 is 1010101.

Below there is an interactive window in which you can practice; it generates random numbers for you to convert them to binary:

Practice
Conversion from Decimals to Binary