\(\newcommand{\newpara}{}
\newcommand{\nats}{\mathbb{N}}
\newcommand{\subcountawry}{\bf{When\ Counting\ Goes\ Awry}}
\newcommand{\seccountingstepscases}{\bf{Counting\ with\ Steps\ and\ Cases}}
\newcommand{\subalgfac}{\bf{Algebra:\ Factorials}}
\newcommand{\seccountingsubsets}{\bf{Counting\ Subsets}}
\newcommand{\secbitstrings}{\bf{Counting\ Bit\ Strings}}
\newcommand{\subhs}{Counting Handshakes}
\newcommand{\circled}[1]{\tikz[baseline=(char.base)]{\node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\newcommand{\xcircle}[1]{\circled{#1}}
\newcommand{\subdiscrete}{What is Discrete Mathematics?}
\newcommand{\sublearning}{Learning Discrete Mathematics}
\newcommand{\exerR}{Recap}
\newcommand{\subcountingawry}{When Counting Goes Awry}
\newcommand{\exerP}{Practice}
\newcommand{\subfactorials}{Algebra: Factorials}
\newcommand{\exerU}{Understand}
\newcommand{\subsubsetschoose}{Subsets and the Binomial Coefficients}
\newcommand{\exerE}{Explore}
\newcommand{\subcombinecount}{Combining Counting Techniques}
\newcommand{\subproofscountnosums}{Proof Format: Combinatorial Proof}
\newcommand{\subbitstrings}{Bit Strings}
\newcommand{\subcountbitstrings}{Number of Bit Strings}
\newcommand{\subrephrasingsubset}{Detour: Rephrasing the Question}
\newcommand{\subexplog}{Algebra: Exponential Notation and Logarithms}
\newcommand{\subbridges}{Crossing Bridges}
\newcommand{\subdefngraph}{The Definition of a Graph}
\newcommand{\subgraphcomp}{Graph Complements}
\newcommand{\subdegseq}{Degree Sequences}
\newcommand{\substdgraphs}{Standard Graphs}
\newcommand{\subadjmat}{The Adjacency Matrix of a Graph}
\newcommand{\subcolormaps}{Coloring Maps}
\newcommand{\subchromatic}{Coloring Graphs}
\newcommand{\subgraphconj}{Graph Conjectures}
\newcommand{\subplanarity}{Planarity}
\newcommand{\subisograph}{Isomorphic Graphs}
\newcommand{\subgraphtrees}{Subgraphs and Trees}
\newcommand{\subnonisograph}{Nonisomorphic Graphs}
\newcommand{\subgraphclassification}{Graph Classification}
\newcommand{\subrobots}{Detour: Robots}
\newcommand{\sublockers}{Opening and Closing Lockers}
\newcommand{\subevenodd}{Even and Odd Integers}
\newcommand{\subdivides}{Divisibility}
\newcommand{\subfractions}{Algebra: Equivalent Fractions}
\newcommand{\subdivalg}{The Division Algorithm, \fn{div}, and \fn{mod}}
\newcommand{\subpolys}{Algebra: Polynomials}
\newcommand{\subpffcases}{Proof Format: Proof by Cases}
\newcommand{\subnotlast}{Not Last Game}
\newcommand{\submod}{The Mod Clock}
\newcommand{\subzn}{The Integers mod $n$}
\newcommand{\subprimes}{Primes and Composites}
\newcommand{\subprimefact}{Prime Factorization}
\newcommand{\subcountdiv}{Detour: Listing and Counting Divisors}
\newcommand{\subgcd}{Greatest Common Divisor}
\newcommand{\subea}{The Euclidean Algorithm}
\newcommand{\subcoprime}{Coprime Integers}
\newcommand{\subandor}{And and Or}
\newcommand{\subpffandor}{Proof Formats: $\land$ and $\lor$ by Cases}
\newcommand{\subequivneg}{Logical Equivalence and Negations}
\newcommand{\subpffcontra}{Proof Format: Contradiction}
\newcommand{\subsetgame}{The Game SET}
\newcommand{\subquant}{Quantifiers}
\newcommand{\subpffquants}{Proof Formats: $\forall$ and $\exists$}
\newcommand{\subcex}{Negating Quantified Statements and Counterexamples}
\newcommand{\subifthen}{Promises: Conditional Statements}
\newcommand{\subpffifthen}{Proof Format: Direct Proof of $\to$}
\newcommand{\subnegcond}{Broken Promises: Negating Conditional Statements}
\newcommand{\subpfforimplication}{Proof Formats: Proof of $\lor$ Using Implication}
\newcommand{\subconv}{The Converse and Biconditional Statements}
\newcommand{\subpffiff}{Proof Format: $\leftrightarrow$}
\newcommand{\subcp}{The Contrapositive}
\newcommand{\subpffcp}{Proof Format: $\to$ Using the Contrapositive}
\newcommand{\subequiv}{Logical Equivalence}
\newcommand{\subneg}{Simplifying Negations}
\newcommand{\subinference}{Logical Inference}
\newcommand{\subinfsetsnumbers}{Infinite sets of numbers}
\newcommand{\subdefnfnnotation}{Function Notation and Vocabulary}
\newcommand{\subpiecewise}{Piecewise-defined Functions}
\newcommand{\subfndotgraphs}{Dot Diagrams and Graphs of Functions}
\newcommand{\subfloorceiling}{Floor and Ceiling}
\newcommand{\subnumberfn}{Number-theoretic Functions}
\newcommand{\subfngraphs}{Graph-theoretic Functions}
\newcommand{\subbitstringfunctions}{Functions Involving Bit Strings}
\newcommand{\suborderedpair}{Ordered Pairs and the Definition of Function}
\newcommand{\subpairing}{Pairings}
\newcommand{\subonetooneonto}{One-to-one and Onto}
\newcommand{\subperms}{Permutations}
\newcommand{\subinverses}{Inverse Functions}
\newcommand{\subpffunique}{Proof Format: Uniqueness}
\newcommand{\subdefnseq}{The Definition of Sequence}
\newcommand{\submodelseq}{Modeling with Explicitly-defined Sequences}
\newcommand{\subseqprimes}{Detour: Sequences Involving Primes}
\newcommand{\subelements}{Elements of a Set}
\newcommand{\subsetbuild}{Set-Builder Notation}
\newcommand{\subsetops}{Set Operations}
\newcommand{\subsubsets}{Subsets of a Set}
\newcommand{\subbsrepsubset}{Bit String Representation of Subsets}
\newcommand{\subsetsofsets}{Sets of Sets}
\newcommand{\subsetfn}{Detour: Set-theoretic Functions}
\newcommand{\subdefnpartition}{The Definition of Partition}
\newcommand{\subselfconj}{Conjugate Partitions}
\newcommand{\subbulgsol}{Collecting Coins}
\newcommand{\subcartprod}{The Cartesian Product of Sets}
\newcommand{\subfncartprod}{Functions Involving Cartesian Products}
\newcommand{\subdefnrelation}{Relations and Their Representations}
\newcommand{\subrelppty}{Properties of Relations}
\newcommand{\subequivclass}{Equivalence Relations and Equivalence Classes}
\newcommand{\subcongmod}{Congruence mod $n$}
\newcommand{\subhanoi}{The Towers of Hanoi}
\newcommand{\subrecdefseq}{Recursively-defined Sequences}
\newcommand{\subntr}{Modeling with Recursively-defined Sequences}
\newcommand{\subpffmathind}{Proof Format: Mathematical Induction}
\newcommand{\subalgind}{Algebra: Evaluating $f(n-1)$}
\newcommand{\subpffindseq}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Rule for a Recursively-defined Sequence}
\newcommand{\submatpowers}{Matrix Products and Powers}
\newcommand{\subpffindmatrix}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Formula for the Power of a Matrix}
\newcommand{\subgroups}{Finite Groups}
\newcommand{\subproperbs}{Proper Bit Strings}
\newcommand{\subrecsets}{Recursively-defined Sets}
\newcommand{\subrecgraphs}{Recursively-defined Graphs}
\newcommand{\subfib}{The Fibonacci Sequence and Higher Order Recursions}
\newcommand{\submodelhigher}{Modeling with Higher Order Recursions}
\newcommand{\subfibpatterns}{Detour: Fibonacci Patterns and Proof}
\newcommand{\subpffstrongind}{Proof Format: Strong Mathematical Induction}
\newcommand{\subhowmanysq}{Counting Squares}
\newcommand{\subfactrep}{Factorial Representations}
\newcommand{\subsigmapi}{Sum and Product Notation}
\newcommand{\subbaseb}{Base $b$ Representation}
\newcommand{\subbinary}{Binary Representation}
\newcommand{\subhex}{Hexadecimal Representation}
\newcommand{\subhexforbinary}{Hex as a Shorthand for Binary}
\newcommand{\subsumconj}{Sum Conjectures}
\newcommand{\subprodconj}{Product Conjectures}
\newcommand{\subsumfib}{Detour: Fibonacci Sums}
\newcommand{\subfactorpolys}{Algebra: Factoring Polynomials}
\newcommand{\subarithtri}{The Arithmetic Triangle}
\newcommand{\subpascalpatterns}{Patterns in the Arithmetic Triangle}
\newcommand{\subbinomthm}{The Binomial Theorem}
\newcommand{\subfactorialbinom}{Explicit Formula for Binomial Coefficients}
\newcommand{\subpffsumproofsind}{Proof Format: Special Case of Mathematical Induction for Proving Sum and Product Formulas}
\newcommand{\subpffcombsums}{Proof Format: Combinatorial Proof of Sums}
\newcommand{\subspecialsum}{Detour: Special Sums}
\newcommand{\subfracalg}{Algebra: Fraction Arithmetic}
\newcommand{\subhotelinf}{Hotel Infinity}
\newcommand{\subdefndiscrete}{The Definition of Discrete}
\newcommand{\seclisting}{Organized Listing}
\newcommand{\vocab}{\textbf}
\newcommand{\str}{\texttt}
\newcommand{\fn}{\texttt}
\newcommand{\bs}{\texttt}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section9.2Binary and Hexadecimal Representations
In Activity 9.1.B, we represent a positive integer using the sum of factorials. A more widely-used representation uses the sum of powers instead. The decimal numbers that we use every day are represented using powers of 10. Historically, 1
people have used a variety of bases. We see remnants of base 60 that the Babylonians and others used (where Iraq is now) in 60 seconds per minute, 60 minutes per hour, or 360\(^\circ\) in a circle. Mayan and Aztec (in Mexico and Central America) used base 20, and there are references to groups of 20 in many modern indigenous languages ranging from Basque (in Spain and France) to Inuit (in Alaska). In Nigeria and Nepal, many languages incorporate base 12, which we see today in the 12-hour clock, 12 inches to a foot, and 12 eggs in a carton. Other bases are possible, but the most commonly-used modern representations are binary, which uses powers of two, and hexadecimal, which uses powers of 16.
for some integer \(k\) where each integer \(a_i = 0,1, \ldots, b-1\text{.}\) For example, in base three we have \(3-1=2\) and so the coefficients can be \(a_i=0,1,2\text{.}\) The integer 15 is represented in base three as
Base 10 is the usual decimal representation where each digit \(a_i = 0, 1, 2, 3, 4, 5, 6, 7, 8\text{,}\) or \(9\text{.}\) We omit the subscript and write \(n = a_ka_{k-1}\cdots a_3a_2a_1a_0\text{.}\) For example, 528 in decimal representation stands for
The most common base systems after base 10 are base two (binary) and base 16 (hexadecimal). Other base systems such as base three (ternary) and base five (quinary) are used mainly to understand base representations. Base eight (octal) was used historically as a shorthand for binary.
Often \(k\) is chosen so that \(a_k > 0\text{,}\) but there are occasions where we write zero in front of a number. For example, we might enter 03 for the month March instead of 3. If we require \(a_k > 0\text{,}\) then the base \(b\) representation of a positive integer is unique.
Since \(50 \lt 81 = 3^4\text{,}\) we only need to use 27, nine, three, and one. Note that \(50-27 = 23\text{,}\)\(23-9-9 = 5\text{,}\)\(5-3=2\text{,}\) and \(2=1+1\) and so we get
When we compare the different representations of the integer 50 from Example 9.2.2 and Example 9.2.3 listed in Table 9.2.4, we see that the larger the base, the shorter the representation of the integer 50 in that base.
Since \(3^{10}=59049\lt 100000\) and \(3^{11} = 177147>100000\text{,}\) we need through \(3^{10}\) but not \(3^{11}\text{.}\) Thus, the base three representation of 100,000 needs 11 digits for the coefficients of
Remark9.2.10The connection between bit strings and binary integers.
In binary representation, the coefficients can be thought of as bits \(\bs{0}\) or \(\bs{1}\text{.}\) Therefore, any bit string represents a binary integer. Note that different bit strings can represent the same integer. For example, \(\bs{110}\text{,}\)\(\bs{0110}\text{,}\)\(\bs{0000110}\) each represent six because
For binary, it is useful to know the powers of two as listed in Table 9.2.11. (We have also included the powers of 16 that we need later for hexadecimal representation.)
Example9.2.12Conversion between decimal and binary.
Convert \((\bs{10110})_2\) to decimal.
Solution.
To determine the highest power of 2 involved, we count in from the right: \(2^0\text{,}\)\(2^1\text{,}\)\(2^2\text{,}\)\(2^3\text{,}\) and finally \(2^4\text{.}\) We have
First, since \(46\lt 64\text{,}\) we only need to use 32, 16, 8, 4, 2, and 1. Notice \(46-32 = 14\text{,}\)\(14-8 = 6\text{,}\) and \(6-4=2\) and so we have
Activity9.2.BConversion between decimal and binary.
Use the definition of binary to convert the representation of integers by hand. That means do not use other algorithms you might have learned or computational technology, except to check.
In hexadecimal (base 16) representation, the coefficients are 0, 1, 2, …, 15. Since the coefficients 10, 11, 12, 13, 14, and 15 are 2-digit numbers we use the letters \(\str{A}\text{,}\)\(\str{B}\text{,}\)\(\str{C}\text{,}\)\(\str{D}\text{,}\)\(\str{E}\text{,}\) and \(\str{F}\) in their place, as shown in Table 9.2.15.
Table9.2.15.Hexadecimal representation of 10, 11, 12, 13, 14, and 15
Example9.2.16Conversion between decimal and hexadecimal.
Convert \((\bs{A5F})_{16}\) to decimal.
Solution.
To determine the highest power of 16 involved, we count in from the right: \(16^0\text{,}\)\(16^1\text{,}\) and then \(16^2\text{.}\) Recalling that \((\bs{A})_{16}=10\) and \((\bs{F})_{16}=15\text{,}\) we have
Note that \(16^2 = 256\) is the highest power of 16 less than 695. Since \(2 \times 256 = 512\text{,}\) we subtract to get \(695 - 512 = 183\text{.}\) Next we calculate \(11 \times 16 = 176\) as the largest multiple of 16 less than 183 and subtract again to get \(183-176=7\text{.}\) Recalling that \(11=(\bs{B})_{16}\text{,}\) we have
Activity9.2.CConversion between decimal and hexadecimal.
Use the definition of hexadecimal to convert the representation of integers by hand. That means do not use other algorithms you might have learned or computational technology, except to check.
In Activity 9.2.B(c), we found \(165 = {(\bs{10100101})_2}\text{.}\) How are the binary and hexadecimal representations of 165 from (b) related? Hint: Look at (c).
We observed from Table 9.2.4 that the larger the base, the shorter the representation of an integer in that base. While binary is longer than base three, five, eight, or 10, hexadecimal is shorter than base three, five, eight, or 10. That is one reason why hexadecimal representation is used, because it helps compress data. But there is another reason. Hexadecimal is an easy-to-read shorthand for the often difficult-to-read binary. Let’s see an example of this shorthand.
Example9.2.18Direct conversion between binary and hexadecimal.
In Example 9.2.16 we saw that \(695 = (\bs{2B7})_{16}\text{.}\) It turns out that \(695 = (\bs{1010110111})_2\text{.}\) Explain how the hexadecimal and binary representations are related.
Solution.
Every four-bit binary number represents a decimal number \(0-15\) and each of those decimal numbers can be written as a single hex digit. There are four bits per hex digit because \(16=2^4\text{.}\) Let’s take the binary representation of 695 and, working from right to left, replace every group of four bits with its single hex digit to get
We used that \((\bs{10})_2= 2 =(\bs{2})_{16}\text{,}\)\((\bs{1011})_2 = 8+2+1=11=(\bs{B})_{16}\text{,}\) and \((\bs{0111})_2 = (\bs{111})_2 = 4+2+1 = 7 = (\bs{7})_{16}\text{.}\)
Convert \((\bs{DE})_{16}\) directly to binary.
Solution.
Noting that \((\bs{D})_{16}=13 = 8 + 4 + 1 = (\bs{1101})_2\) and \((\bs{E})_{16}=14 = 8 + 4 + 2 = (\bs{1110})_2\text{,}\) we replace each hex digit with its 4-bit binary representation to get
Convert \((41)_{16}\) directly to binary.
Solution.
Noting that \((4)_{16}= 4 = (0100)_2\) and \((1)_{16} = 1 = (0001)_2\text{,}\) we replace each hex digit with its 4-bit binary representation, adding \(\bs{0}\) s in front as needed, to get
Activity9.2.DConversion between binary and hexadecimal.
In this problem use the definition of binary and hexadecimal to convert the representation of integers by hand. That means do not use other algorithms you might have learned or computational technology, except to check.
Convert \((\bs{E7})_{16}\) directly to binary. That means without converting to decimal first.
Many exercises in this section could be answered using a calculator or online resources. Since the purpose of the exercises is to help you understand the representation, please work out the solutions by hand and be sure to show work. Also, even if you know a simpler conversion algorithm, be sure to use the formal process outlined in this section.
The results of this problem are used to prove the uniqueness of the base \(b\) representation.
The largest integer we can represent in 3 digits in base 3 is \((222)_3\) and in base 5 is \((444)_5\text{.}\) Convert each of these integers to decimal.
For each integer, determine how many bits are needed for the binary representation without finding the binary representation. Hint: Consult Table 9.2.11.
Hint: You can write the answer in summation notation as \(\displaystyle \sum_{k=\underline{\hspace{.1in}}}^m\underline{\hspace{.2in}}\text{.}\) Check that the summand involves \(2^k\) (not \(2^m\)).
For each integer, determine how many hex digits are needed for the hexadecimal representation without finding the hexadecimal representation. Hint: Consult Table 9.2.11.
What is the largest integer we can represent in \(m\) hex digits in hexadecimal? Your answer should be a sum. Your answer should not have any letters in it.
Digital colors are represented in hex. The first two digits control the amount of red, from \((\bs{00})_{16}=0\) (none) to \((\bs{FF})_{16}=255\) (fully saturated). The next two digits control the amount of green, and the last two digits control the amount of blue.
Subsection9.2.IExercises for 9.2.D Hex as a Shorthand for Binary
23.Practice.
In Exercise 11 and Exercise 18, we wrote each of the following integers in both binary and hexadecimal representation. Confirm that the correspondence from Example 9.2.18 holds.
