10.3. Binary Operations#

In order for binary numbers to be useful in your computer, it needs to be able to perform operations with them, such as addition, subtraction, multiplication, etc. The same algorithms you likely learned with base-10 numbers will still be valid when working in other base number systems as well.

Addition of Binary Numbers#

Suppose you wanted to add the numbers \(19\) and \(43\) using their binary representations. Writing out each and stacking them vertically results in:

\[\begin{split} \begin{array}{r} \texttt{10011} \\ +\text{ } \texttt{101011} \\ \hline \end{array} \end{split}\]

You can carry out the addition in a similar way as when working with base-10 numbers. Begin in the position with lowest value, the \(2^0\) position found furthest to the right. Adding this column, we have \(1 + 1 = 10\) (“one” plus “one” equals “two”, written in binary).

\[\begin{split} \begin{array}{r} \texttt{ 1 } \\ \texttt{10011} \\ +\text{ } \texttt{101011} \\ \hline \texttt{ 0} \end{array} \end{split}\]

In the second right-most place, the addition is \(1 + 1 + 1 = 11\), resulting in a \(1\) with a “carry” of \(1\).

\[\begin{split} \begin{array}{r} \texttt{ 11 } \\ \texttt{10011} \\ +\text{ } \texttt{101011} \\ \hline \texttt{ 10} \end{array} \end{split}\]

The rest of the addition is shown below

\[\begin{split} \begin{array}{r} \texttt{ 11 } \\ \texttt{10011} \\ +\text{ } \texttt{101011} \\ \hline \texttt{111110} \end{array} \end{split}\]

Converting \(111110\) to decimal should confirm the sum of \(19\) and \(43\):

\[ 1\cdot2^5 + 1\cdot2^4 + 1\cdot2^3 + 1\cdot2^2 + 1\cdot2^1 + 0\cdot2^0 = 32 + 16 + 8 + 4 + 2 = 62 \]

Bitwise Addition (XOR)#

Adding binary numbers together helps illustrate that adding number yields the same result no matter which base we choose to work in. However, most cryptographic operations with binary numbers use bitwise addition, denoted by the symbol \(\oplus\). For binary numbers, bitwise addition is equivalent to adding each digit modulo \(2\). Note that there is no carrying when completing bitwise addition. The lack of carrying is an important feature of bitwise addition that will become important when you starting using it to encipher messages.

For each bit there are only 4 possibilities:

  • \(0 + 0 \equiv 0 \pmod{2}\)

  • \(1 + 0 \equiv 1 \pmod{2}\)

  • \(0 + 1 \equiv 1 \pmod{2}\)

  • \(1 + 1 \equiv 0 \pmod{2}\)

So, the bitwise addition of 2 binary numbers would look like:

\[\begin{split} \begin{array}{r} \texttt{101101110100} \\ \oplus\text{ } \texttt{101001010010} \\ \hline \texttt{000100100110} \end{array} \end{split}\]

This operation is also sometimes referred to as the exclusive or logic operator, since it returns a True value (represented as a \(1\)) only if the first digit or second digit is a \(1\), but not if both are a \(1\).