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:
Mathematicians call this decimal representation of a number. They might prefer to write this as
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. 1
Here is how a computer counts to 8 in binary:
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:
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{.}\)
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
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:
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
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
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:
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. 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{.}\)
Lemma 2.2.3.
Nim addition satisfies the following conditions for any integers \(a,b,c\text{:}\)
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{.}\)
Suppose that \(a \oplus c = b \oplus c\text{.}\) Since \(c \oplus c = 0\) and nim addition is associative, we have
We will need Lemma 2.2.4 in Section [cross-reference to target(s) "sec-sumgames" missing or not unique]
.