Cryptography Reference
In-Depth Information
CONVERTING DECIMAL TO BINARY
Converting a decimal number into binary is essentially just the reverse of the
process for converting binary into decimal. Recall that a binary number such as
1101
2
specifies a sum of multiples of powers of 2. These multiples can only take
the values 0 or 1, so a binary number really specifies a sum of
some of
the powers
of 2. More precisely:
• if the multiple is 0 then the corresponding power of 2 is not included in the sum;
• if the multiple is 1 then the corresponding power of 2 is included in the sum.
In fact any number can be
uniquely
expressed as a sum of powers of 2.
So the question of how to convert a given decimal number into binary is
equivalent to asking precisely which of the powers of 2 add up to that decimal
number.
For a small number such as 14 we can easily determine this by trial and error.
It does not take very long to work out that the powers of 2 that add up to 14 are
8, 4 and 2. Thus, by reversing the binary to decimal process, we see that:
14
10
=
8
+
4
+
2
=
(1
×
8)
+
(1
×
4)
+
(1
×
2)
+
(0
×
1)
2
3
)
2
2
)
2
1
)
2
0
)
=
(1
×
+
(1
×
+
(1
×
+
(0
×
1110
2
.
In general, and in particular to convert large decimal numbers into binary, we
need some kind of algorithm (system) for working out the binary equivalent of
a decimal number. For simplicity, we will illustrate this process using a small
number, namely 25
10
.
1.
Find the highest power of 2 that is smaller than 25
. Clearly it is not possible for
a power of 2 that is larger than 25 to be part of the sum of powers of 2 that
adds up to 25, so we find the largest power of 2 less than 25. This is 16. Thus
25
10
can be expressed as a sum of powers of 2 that are all less than or equal
to 16. In other words:
=
25
10
=
(?
×
16)
+
(?
×
8)
+
(?
×
4)
+
(?
×
2)
+
(?
×
1)
.
2.
Determine whether each of the ? symbols is 0 or 1
. Consider the ? coefficient
next to 16. All of the remaining powers of 2 (8, 4, 2 and 1) only add up to 15.
Thus we must have 16 in our sum of powers of 2 that add up to 25, otherwise
we could only sum to 15. Hence the coefficient of 16 must be 1. So:
25
10
=
(1
×
16)
+
(?
×
8)
+
(?
×
4)
+
(?
×
2)
+
(?
×
1)
.
Now the remaining four powers of 2 must add to 25
−
16
=
9. Consider the
? coefficient next to 8. All of the remaining powers of 2 (4, 2 and 1) only add
up to 7. Thus we must have 8 in our sum of powers of 2 that add up to 25,
