Games: Binary Representation of Numbers

Section 2.2 Binary Representation of Numbers

When you see the number 263, there is no ambiguity. You see "two hundred sixty three."

Of course this interpretation uses the standard convention for how to read numbers. That is, the rightmost number is the "ones place," the middle digit is the "tens place" and the left digit is the "hundreds place." You have gotten so used to this convention that it is second nature to you. But when you originally learned it, your teacher probably had you break this number down like so:

\begin{equation*} 263 = 200 + 60 + 3. \end{equation*}

Mathematicians call this decimal representation of a number. They might prefer to write this as

\begin{equation*} 263 = (2 \times 10^2) + (6 \times 10^1) + (3 \times 10^0), \end{equation*}

and they call this the decimal expansion of the number. Of course, decimal refers to the fact that we have ten digits in our number system \(0,1,2,3,4,5,6,7,8,9\text{.}\) When we need to count above 9, we reuse these digits, but shift them over by one to represent multiples of 10. This scheme goes from 10 up to 99, where we must add another digit to represent multiples of 100, and so on. Every positive integer has a unique decimal representation, and this uniqueness is crucial.

However, the use of ten different digit symbols is a choice. Undoubtedly, this is a convenient choice for obvious reasons. Computers do not use a decimal representation of numbers because they don't have fingers and toes. Instead, they are built out of switches that have two positions: "on" and "off." The "on" state corresponds to having electrical current present, and it is assigned the value "1." The "off" state corresponds to no current, and it is assigned the value "0."

In other words, the "digits" in a digital computer have two states. So in the computer worldview, a binary number system (that only uses the symbols 0 and 1) fits its worldview much better than a decimal number system.¹

If we were visited by aliens with 17 polyps on their one sensory pseudopod, you can bet that they will use 17 digits in their number system.

Here is how a computer counts to 8 in binary:

\begin{equation*} \begin{array}{|r|r|r|} \hline \mbox{decimal} & \mbox{binary} & \mbox{binary expansion} \\ \hline 1 & 1 & ( 1 \times 2^0)\\ 2 & 10 & ( 1 \times 2^1) + ( 0 \times 2^0) \\ 3 & 11 & ( 1 \times 2^1) + ( 1 \times 2^0) \\ 4 & 100 & ( 1 \times 2^2) +( 0 \times 2^1) + ( 0 \times 2^0)\\ 5 & 101 & ( 1 \times 2^2) +( 0 \times 2^1) + ( 1 \times 2^0)\\ 6 & 110 & ( 1 \times 2^2) +( 1 \times 2^1) + ( 0 \times 2^0)\\ 7 & 111 & ( 1 \times 2^2) +( 1 \times 2^1) + ( 1 \times 2^0)\\ 8 & 1000 & ( 1 \times 2^3) +( 0 \times 2^2) +( 0 \times 2^1) + ( 0 \times 2^0)\\ \hline \end{array} \end{equation*}

In a decimal representation, we have the "ones place," the "tens place", the "hundreds place" and so on. In a binary representation, we have the "ones place" the "twos place", the "fours place", the "eights place" and so on. Furthermore, there are only two digits employed in the binary representation: 0 and 1. Just as for a decimal representation, the binary representation of a number is unique.

Subsection 2.2.1 Converting between number systems

Let's practice some conversions between binary representations and decimal representations. Going from binary to decimal is pretty straightforward. Here are some examples:

\begin{equation*} \begin{array}{|r|c|c|} \hline \mbox{binary} & \mbox{binary expansion} & \mbox{decimal} \\ \hline 01011 & \phantom{1}0 + 8 + 0 + 2 + 1 & 11 \\ 10010 & 16+0 + 0+ 2+ 0 & 18 \\ 11001 & 16+ 8+0 + 0 +1 & 25 \\ 11111 & 16+ 8+4+2+1 & 31 \\ \hline \end{array} \end{equation*}

Converting from decimal to binary is a bit harder because most people haven't memorized the powers of 2. Here are the first few values of \(2^n\text{.}\)

\begin{equation*} \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline 2^0 & 2^1 & 2^2 & 2^3 & 2^4 & 2^5 & 2^6 & 2^7 & 2^8 & 2^9 & 2^{10} \\ \hline 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512 & 1024 \\ \hline \end{array} \end{equation*}

Here is how to find the binary representation of a positive integer \(n\text{:}\)

Algorithm 2.2.1. Finding the Binary Representation.

Given a positive integer \(n\text{:}\)

Find the largest \(k\) such that \(2^k \leq n\)
Repeat step 1 for the remainder \(n - 2^k\) until you reach 0.
This gives you the expansion \(n= 2^{k_1} + 2^{k_2} + \cdots + 2^{k_r}\text{.}\)
The binary representation of \(n\) consists of \(k_1+1\) digits. It has a 1 in the positions \(k_1, k_2, \ldots, k_r\text{,}\) where the rightmost position is indexed by 0. The remaining digits are each 0.

Here are some examples of converting from decimal representation to binary representation

\begin{equation*} \begin{array}{|r|rcl|r|} \hline \mbox{decimal} & \mbox{decomposing into powers of 2} &&& \mbox{binary} \\ \hline 53 & 32 + 16 + 4 +1 &=& 2^5 + 2^4 + 2^2 + 2^0 & 110101 \\ 44 & 32 + 8 + 4 &=& 2^5 + 2^3 + 2^2 & 101100 \\ 31 & 16 + 8 + 4 +2 +1 &=& 2^4 + 2^3 + 2^2 + 2^1+2^0 & 11111 \\ 80 & 64 + 16 &=& 2^6 + 2^4 & 1010000 \\ \hline \end{array} \end{equation*}

Finally, it is often useful to add leading zeros to a binary number, so that all the numbers under consideration have the same length. In other words, we might replace the list of binary numbers \(0\text{,}\) \(101\text{,}\) \(1100\) with the representations \(0000\text{,}\) \(0101\text{,}\) \(1100\) so that each of these numbers uses four symbols.

Subsection 2.2.2 Addition of Binary Numbers

Addition of binary numbers follows rules analogous to decimal addition: we must carry over to the next column whenever we exceed the digit symbols available. For us, this means that whenever we have a column containing \(1+1\text{,}\) we must enter a 0 in that column and carry over a 1 to the next column. For example, we have:

\begin{equation} \begin{array}{cccccc} \begin{array}{r} 101 \\ + 011 \\ \hline 1000 \end{array}, & \qquad \begin{array}{r} 111 \\ + 111 \\ \hline 1110 \end{array}, & \qquad \begin{array}{r} 10110 \\ +00101\\ \hline 11011 \end{array}, & \qquad \begin{array}{r} 01101 \\ + 10110 \\ \hline 100011 \end{array}. \end{array}\label{eqn-binary-addition}\tag{2.2.1} \end{equation}

You should check that you get the same answers for these sums when you convert the numbers to decimal representations.

Subsection 2.2.3 Nim Addition of Binary Numbers

The key to cracking the game of nim is to use a different type of addition of binary numbers, which we will call nim addition. We use the symbol \(\nimsum\) to denote this operation.

Nim addition of binary numbers is actually easier than regular binary addition. You perform the addition without carrying over! In other words, regular addition gives \(1+1 = 10\text{,}\) while Nim addition gives \(1 \nimsum 1 = 0\text{.}\) For example, taking the nim sum of the numbers in equation (2.2.1), we have

\begin{equation} \begin{array}{cccccc} \begin{array}{r} 101 \\ \nimsum 011 \\ \hline 110 \end{array}, & \qquad \begin{array}{r} 111 \\ \nimsum 111 \\ \hline 000 \end{array}, & \qquad \begin{array}{r} 10110 \\ \nimsum 00101\\ \hline 10011 \end{array}, & \qquad \begin{array}{r} 01101 \\ \nimsum 10110 \\ \hline 11011 \end{array}. \end{array}\label{eqn-nim-addition}\tag{2.2.2} \end{equation}

As you can see from the answers in equations (2.2.1) and (2.2.2), nim sum is completely different from regular addition.

In fact, nim sums have other applications. For example, in computer science this operation evaluated by taking the "bitwise exclusive or" of the two numbers. For the game of Nim, we will see that taking the nim sums of the heap sizes reveals whether we are in an \(\cN\)-position or a \(\cP\)-position.

We note that there is nothing wrong with taking the nim sum of two numbers written in decimal notation. To do so, we must convert to binary notation, perform the nim sum, and then convert back to decimal. Here is an example: \(7 \nimsum 3 = 4\) because

\begin{equation*} \label{eqn:nimsum-example} \underbrace{7 \nimsum 3}_{\mbox{decimal}} = \underbrace{111 \nimsum 011}_{\mbox{binary}} = \underbrace{100}_{\mbox{binary}} = \underbrace{4}_{\mbox{decimal}}. \end{equation*}

Finally, it is easy to take the nim sum of multiple numbers simultaneously.

Algorithm 2.2.2. Finding the Nim Sum of Mutiple Numbers.

Line up the binary numbers, as usual.
Place a 1 in the columns where there are an odd number of 1's.
Place a 0 in the columns with an even number of 1's.

Here is an example of the nim sum of 4 binary numbers:

\begin{equation*} \begin{array}{r} 1\,1\,0\,1\,1 \\ \nimsum \,0\,1\,0\,0\,1 \\ \nimsum \,0\,0\,1\,1\,1 \\ \nimsum \,1\,1\,0\,0\,0 \\ \hline 0 \, 1 \, 1 \,0 \, 1. \end{array} \end{equation*}

When written in decimal notation, this says that \(27 \nimsum 9 \nimsum 7 \nimsum 24 = 13\text{.}\)

We end this section with two final lemmas.

Lemma 2.2.3.

Nim addition satisfies the following conditions for any integers \(a,b,c\text{:}\)

Additive inverse law: \(a \oplus a = 0\text{,}\)
Commutative law: \(a \oplus b = b \oplus a\text{,}\)
Associative law: \((a \oplus b) \oplus c = a \oplus (b \oplus c)\text{.}\)

Proof.

We leave the proof of these three properties for the exercises.

Lemma 2.2.4. Cancellation Law.

If \(a \oplus c = b \oplus c\) then \(a=b\text{.}\)

Proof.

Suppose that \(a \oplus c = b \oplus c\text{.}\) Since \(c \oplus c = 0\) and nim addition is associative, we have

\begin{equation*} a= a \oplus 0 = a \oplus (c \oplus c) = (a \oplus c) \oplus c = (b \oplus c) \oplus c= b \oplus (c \oplus c) = b \oplus 0 = b. \end{equation*}

We will need Lemma 2.2.4 in Section [cross-reference to target(s) "sec-sumgames" missing or not unique].