Discrete Mathematics for Computer Science

Subsection 1.4.1 Grouping by Twos

Recall that the set of positive integers, \(\mathbb{P}\text{,}\) is \(\{1, 2, 3, . . . \}\text{.}\) Positive integers are naturally used to count things. There are many ways to count and many ways to record, or represent, the results of counting. For example, if we wanted to count five hundred twenty-three apples, we might group the apples by tens. There would be fifty-two groups of ten with three single apples left over. The fifty-two groups of ten could be put into five groups of ten tens (hundreds), with two tens left over. The five hundreds, two tens, and three units is recorded as 523. This system of counting is called the base ten positional system, or decimal system. It is quite natural for us to do grouping by tens, hundreds, thousands, \(\dots\) since it is the method that all of us use in everyday life.

The term positional refers to the fact that each digit in the decimal representation of a number has a significance based on its position. Of course this means that rearranging digits will change the number being described. You may have learned of numeration systems in which the position of symbols does not have any significance (e.g., the ancient Egyptian system). Most of these systems are merely curiosities to us now.

The binary number system differs from the decimal number system in that units are grouped by twos, fours, eights, etc. That is, the group sizes are powers of two instead of powers of ten. For example, twenty-three can be grouped into eleven groups of two with one left over. The eleven twos can be grouped into five groups of four with one group of two left over. Continuing along the same lines, we find that twenty-three can be described as one sixteen, zero eights, one four, one two, and one one, which is abbreviated \(10111_{\textrm{two}}\text{,}\) or simply \(10111\) if the context is clear.

Subsection 1.4.2 A Conversion Algorithm

The process that we used to determine the binary representation of \(23\) can be described in general terms to determine the binary representation of any positive integer \(n\text{.}\) A general description of a process such as this one is called an algorithm. Since this is the first algorithm in the book, we will first write it out using less formal language than usual, and then introduce some “algorithmic notation.” We will cover algorithms specifically in Chapter 9

1. Start with an empty list of bits.

2. Step Two: Assign the variable \(k\) the value \(n\text{.}\)

3. Step Three: While \(k\)'s value is positive, continue performing the following three steps until \(k\) becomes zero and then stop.

   1. divide \(k\) by 2, obtaining a quotient \(q\) (often denoted \(k \textrm{ div } 2\)) and a remainder \(r\) (denoted \((k \bmod 2)\)).

   2. attach \(r\) to the left-hand side of the list of bits.

   3. assign the variable \(k\) the value \(q\text{.}\)

The notation that we will use to describe this algorithm and all others is called pseudocode, an informal variation of the instructions that are commonly used in many computer languages. Read the following description carefully, comparing it with the informal description above. Chapter 9, which contains a general discussion of the components of the algorithms in this book, should clear up any lingering questions. Anything after // are comments.

Subsection 1.4.3 SageMath Note: Binary Conversion Algorithm

Here is a Sage version of the algorithm with two alterations. It outputs the binary representation as a string, and it handles all integers, not just positive ones.

Now that you've read this section, you should get this joke.