Binary Conversions

Section A.2 Binary Conversions

Binary is the same idea as base 26 but with base 2. We only have two binary digits (called bits) namely 0 and 1. This is important for computers as it corresponds to an electric circuit being off or on.

Example A.2.1.

Convert 01101101 to decimal. Each bit (0 or 1) corresponds to the appropriate power of 2.

\begin{equation*} 01101101=0\cdot2^7+1\cdot2^6+1\cdot2^5+0\cdot2^4+1\cdot2^3+1\cdot2^2+0\cdot2^1+1\cdot2^0 \end{equation*}

\begin{equation*} =2^6+2^5+2^3+2^2+1=64+32+8+4+1=109 \end{equation*}

In general, if \(e_k e_{k-1}\cdots e_1 e_0\) is the binary representation for \(j\text{,}\) then \(j=e_k \cdot 2^k+e_{k-1} \cdot 2^{k-1}+\cdots+ e_1 \cdot 2^1 + e_0 \cdot 2^0\text{.}\)

Example A.2.2.

Convert 78 to binary.

Method 1: Find highest power of 2 that is less than 78. \(64=2^6\) is the highest such power of 2 and \(78=64+14\text{.}\) Repeat the process with \(14=8+6\) and so on to get \(78=64+8+4+2=2^6+2^3+2^2+2^1\text{.}\) This corresponds to 1001110 in binary.

Method 2: Repeatedly apply the division algorithm to quotients when dividing by 2 until the quotient \(\leq 2\text{.}\)

\begin{align*} 78\amp=2(39)\\ 39\amp=2(19)+1\\ 19\amp=2(9)+1\\ 9\amp=2(4)+1\\ 4\amp=2(2) \end{align*}

Rewrite using powers of 2 in reverse.

\begin{align*} 4\amp=2^2\\ 9\amp=2(4)+1=2(2^2)+1=2^3+1\\ 19\amp=2(9)+1=2(2^3+1)+1=2^4+2+1\\ 39\amp=2(19)+1=2(2^4+2+1)+1=2^5+2^2+2+1\\ 78\amp=2(39)=2(2^5+2^2+2+1)=2^6+2^3+2^2+2^1 \end{align*}

This corresponds to 1001110 in binary.

Many current cryptographic algorithms are specified in terms of bit size. Since we are more familiar with decimal numbers, we will want to compare bit size to the number of decimal digits in a number.

Example A.2.3.

For example, how many decimal digits are there in a 15 bit number? To answer this we really want to know how many decimal digits there are in the the largest 15 bit number. The largest 15 bit number contains all ones, that is \(111111111111111\text{.}\) We could convert this to decimal according to the formula \(2^{14}+2^{13}+ \cdots + 2^1 +1\) but its much easier to add 1 to this number, \(111111111111111+1=1000000000000000\text{.}\) This is just \(2^{15}\text{.}\) So how many decimal digits in \(2^{15}\text{?}\) Of course, we could just compute \(2^{15}=32768\) and count that there are five digits, but for larger bit sizes we will not want to count all the digits. So let's examine this another way. In order to write \(2^{15}\) in decimal we need to know the largest power of 10 that is less than \(2^{15}\text{.}\) That is, we want to find the integer \(k\) such that \(2^{15}\gt 10^k\) but \(2^{15} \lt 10^{k+1}\text{.}\) The easiest way to do that is to find the real number \(x\) such that \(2^{15}=10^x\text{.}\) We can now solve for this using logarithms! Using log base 10 we have:

\begin{equation*} \log_{10}(2^{15})=\log_{10}(10^{x}) \end{equation*}

and

\begin{equation*} 15\log_{10}(2)=x\text{.} \end{equation*}

So \(x=4.51\) and we can see we need five decimal places. Remember that we need one more than the largest power of 10 since we start with the ones (or \(10^0\)) digit.

One important binary operation is the xor (short for exclusive or) operation. This operation can be thought of as mod 2 addition at the bit level with no carrying. That is, \(0\oplus0=0\) since \(0+0 \pmod{2} =0\text{,}\) \(1\oplus0=1\) since \(1+0 \pmod{2} =1\text{,}\) and \(1\oplus1=0\) since \(1+1 \pmod{2} =0\text{.}\) The same operation is applied to each bit for longer bit strings. For example, \(01001 \oplus 11100 = 10101\text{.}\)