How Computers Really Work PDF

HOW COMPUTERS R E A L LY W O R K A H A N D S - O N G U I D E T O T H E I N N E R W O R K I N G S O F T H E M A C H I N E MATTHEW JUSTICE HOW COMPUTERS REALLY WORK  HOW COMPUTERS REALLY WORK A Hands-On Guide to the Inner Workings of the Machi...

HOW COMPUTERS R E A L LY W O R K A H A N D S - O N G U I D E T O T H E I N N E R W O R K I N G S O F T H E M A C H I N E MATTHEW JUSTICE HOW COMPUTERS REALLY WORK  HOW COMPUTERS REALLY WORK A Hands-On Guide to the Inner Workings of the Machine b y Ma t t h ew J u s t i c e San Francisco HOW COMPUTERS REALLY WORK. Copyright © 2021 by Matthew Justice. All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, elec- tronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, with- out the prior written permission of the copyright owner and the publisher. ISBN-13: 978-1-71850-066-2 (print) ISBN-13: 978-1-71850-067-9 (ebook) Publisher: William Pollock Execuitve Editor: Barbara Yien Production Editor: Katrina Taylor Developmental Editor: Alex Freed Project Editor: Dapinder Dosanjh Cover Design: Gina Redman Interior Design: Octopod Studios Technical Reviewers: William Young, John Hewes, and Bryan Wilhem Copyeditor: Happenstance Type-O-Rama Compositor: Happenstance Type-O-Rama Proofreader: Happenstance Type-O-Rama The following images are reproduced with permission: Figures 7-7, 7-9, 7-10, and 7-11 ALU symbol was altered from the image created by Eadthem and is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license (https://commons.wikimedia.org/wiki/File:ALU_ symbol-2.svg). Figures 11-3, 11-5, 11-14, 11-15, 11-16, 11-17, 12-4, 12-8, 12-9, 12-10, 13-5, 13-9 server icon is courtesy of Vecteezy.com. For information on distribution, translations, or bulk sales, please contact No Starch Press, Inc. directly: No Starch Press, Inc. 245 8th Street, San Francisco, CA 94103 phone: 1.415.863.9900; [email protected] www.nostarch.com Library of Congress Cataloging-in-Publication Data: Names: Justice, Matthew, author. Title: How Computers Really Work : a hands-on guide to the inner workings of the machine / Matthew Justice. Description: San Francisco : No Starch Press, Inc., | Includes index. Identifiers: LCCN 2020024168 (print) | LCCN 2020024169 (ebook) | ISBN 9781718500662 (paperback) | ISBN 1718500661 (paperback) | ISBN 9781718500679 (ebook) Subjects: LCSH: Electronic digital computers--Popular works. Classification: LCC QA76.5.J87 2020 (print) | LCC QA76.5 (ebook) | DDC 004--dc23 LC record available at https://lccn.loc.gov/2020024168 LC ebook record available at https://lccn.loc.gov/2020024169 No Starch Press and the No Starch Press logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The information in this book is distributed on an “As Is” basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it. To my family, who believed in me while I tried something new. About the Author Matthew Justice is a software engineer. He spent 17 years at Microsoft where he took on various roles, including debugging the Windows kernel, devel- oping automated fixes, and leading a team of engineers responsible for building diagnostic tools and services. He has worked on low-level software (the operating system) and on software far removed from the underlying hardware (such as web applications). Matthew has a degree in electrical engineering. When he’s not writing code or building circuits, Matthew enjoys spending time with his family, hiking, reading, arranging music, and playing old video games. About the Tech Reviewers Dr. Bill Young is Associate Professor of Instruction in the Deptartment of Computer Science at the University of Texas at Austin. Prior to joining the UT faculty in 2001, he had 20 years of experience in the industry. He special- izes in formal methods and computer security, but often teaches computer architecture, among other courses. Bryan Wilhelm is a software engineer. He has degrees in mathematics and computer science and has been working at Microsoft for 20 years in roles ranging from debugging the Windows kernel to developing business applica- tions. He enjoys reading, science-fiction movies, and classical music. John Hewes began connecting electrical circuits at an early age, moving on to electronics projects as a teenager. He later earned a physics degree and continued to develop his interest in electronics, helping school students with their projects while working as a science technician. John has taught electron- ics and physics up to an advanced level in the United Kingdom and ran a school electronics club for children aged 11 to 18 years, setting up the website http://www.electronicsclub.info/ to support the club. He believes that everyone can enjoy building electronics projects, regardless of their age or ability.  BRIEF CONTENTS Acknowledgments.................................................... xvii Introduction......................................................... xix Chapter 1: Computing Concepts............................................ 1 Chapter 2: Binary in Action.............................................. 17 Chapter 3: Electrical Circuits............................................. 31 Chapter 4: Digital Circuits............................................... 53 Chapter 5: Math with Digital Circuits........................................ 73 Chapter 6: Memory and Clock Signals...................................... 91 Chapter 7: Computer Hardware.......................................... 117 Chapter 8: Machine Code and Assembly Language............................ 137 Chapter 9: High-­Level Programming....................................... 159 Chapter 10: Operating Systems.......................................... 193 Chapter 11: The Internet................................................ 233 Chapter 12: The World Wide Web........................................ 261 Chapter 13: Modern Computing.......................................... 291 Appendix A: Answers to Exercises........................................ 319 Appendix B: Resources................................................ 333  CONTE NT S IN DE TA IL ACKNOWLEDGMENTS XVII INTRODUCTION XIX Who Is This Book For?............................................... xx About This Book................................................... xx About Exercises and Projects.............................................. xxi My Computing Journey............................................. xxii 1 COMPUTING CONCEPTS 1 Defining a Computer................................................. 2 Analog and Digital.................................................. 2 The Analog Approach......................................... 2 Going Digital............................................... 4 Number Systems................................................... 5 Decimal Numbers............................................ 5 Binary Numbers.............................................. 6 Bits and Bytes...................................................... 8 Prefixes.......................................................... 9 Hexadecimal..................................................... 11 Summary........................................................ 15 2 BINARY IN ACTION 17 Representing Data Digitally........................................... 18 Digital Text................................................ 18 ASCII.................................................... 19 Digital Colors and Images...................................... 21 Approaches for Representing Colors and Images...................... 22 Interpreting Binary Data....................................... 24 Binary Logic...................................................... 25 Summary........................................................ 30 3 ELECTRICAL CIRCUITS 31 Electrical Terms Defined.............................................. 32 Electric Charge............................................. 32 Electric Current............................................. 32 Voltage................................................... 33 Resistance................................................. 33 Water Analogy............................................. 34 Ohm’s Law....................................................... 35 Circuit Diagrams................................................... 35 Kirchhoff’s Voltage Law.............................................. 38 Circuits in the Real World............................................ 40 Light-­Emitting Diodes................................................ 42 Summary........................................................ 44 Project #1: Build and Measure a Circuit...................................... 45 Project #2: Build a Simple LED Circuit....................................... 50 4 DIGITAL CIRCUITS 53 What Is a Digital Circuit?............................................. 54 Logic with Mechanical Switches........................................ 54 The Amazing Transistor.............................................. 57 Logic Gates...................................................... 59 Designing with Logic Gates........................................... 61 Integrated Circuits.................................................. 62 Summary....................................................... 65 Project #3: Build Logical Operators (AND, OR) with Transistors.................... 66 Project #4: Construct a Circuit with Logic Gates................................ 68 5 MATH WITH DIGITAL CIRCUITS 73 Binary Addition................................................... 74 Half Adders...................................................... 76 Full Adders....................................................... 78 A 4-bit Adder..................................................... 80 Signed Numbers................................................... 81 Unsigned Numbers................................................. 85 Summary........................................................ 87 Project #5: Build a Half Adder............................................ 89 6 MEMORY AND CLOCK SIGNALS 91 Sequential Logic Circuits and Memory.................................... 91 The SR Latch...................................................... 92 Using the SR Latch in a Circuit......................................... 95 Clock Signals..................................................... 98 JK Flip-­Flops...................................................... 99 T Flip-­Flops...................................................... 100 Using a Clock in a 3-Bit Counter....................................... 101 Summary....................................................... 103 Project #6: Construct an SR Latch Using NOR Gates............................ 104 Project #7: Construct a Basic Vending Machine Circuit.......................... 105 Project #8: Add a Delayed Reset to the Vending Machine Circuit.................. 107 Project #9: Using a Latch as a Manual Clock................................. 109 Project #10: Test a JK Flip-­Flop............................................ 111 Project #11: Construct a 3-bit Counter....................................... 113 7 COMPUTER HARDWARE 117 Computer Hardware Overview........................................ 117 Main Memory................................................... 119 xii   Contents in Detail Central Processing Unit (CPU)........................................ 122 Instruction Set Architectures.................................... 123 CPU Internals.............................................. 125 Clock, Cores, and Cache..................................... 127 Beyond Memory and Processor....................................... 130 Secondary Storage......................................... 130 Input/Output.............................................. 131 Bus Communication................................................ 134 Summary....................................................... 135 8 MACHINE CODE AND ASSEMBLY LANGUAGE 137 Software Terms Defined............................................. 138 An Example Machine Instruction....................................... 139 Calculating a Factorial in Machine Code................................. 141 Summary....................................................... 144 Project #12: Factorial in Assembly......................................... 145 Project #13: Examining Machine Code...................................... 155 9 HIGH-­LEVEL PROGRAMMING 159 High-­Level Programming Overview..................................... 160 Introduction to C and Python......................................... 160 Comments...................................................... 161 Variables....................................................... 162 Variables in C............................................. 162 Variables in Python......................................... 163 Stack and Heap Memory............................................ 164 The Stack................................................ 164 The Heap................................................ 165 Math.......................................................... 166 Logic.......................................................... 169 Bitwise Operators.......................................... 169 Boolean Operators......................................... 170 Program Flow.................................................... 172 If Statements.............................................. 172 Looping................................................. 173 Functions....................................................... 174 Defining Functions.......................................... 175 Calling Functions........................................... 176 Using Libraries............................................. 177 Object-­Oriented Programming........................................ 177 Compiled or Interpreted............................................. 179 Calculating a Factorial in C.......................................... 180 Summary....................................................... 183 Project #14: Examine Variables........................................... 184 Project #15: Change the Type of Value Referenced by a Variable in Python.......... 186 Project #16: Stack or Heap.............................................. 187 Project #17: Write a Guessing Game....................................... 189 Project #18: Use a Bank Account Class in Python.............................. 190 Project #19: Factorial in C............................................... 191 Contents in Detail   xiii 10 OPERATING SYSTEMS 193 Programming Without an Operating System............................... 193 Operating Systems Overview......................................... 195 Operating System Families........................................... 197 Kernel Mode and User Mode......................................... 199 Processes....................................................... 200 Threads........................................................ 202 Virtual Memory.................................................. 204 Application Programming Interface (API)................................. 207 The User Mode Bubble and System Calls................................. 209 APIs and System Calls.............................................. 211 Operating System Software Libraries.................................... 212 Application Binary Interface.......................................... 214 Device Drivers................................................... 214 Filesystems...................................................... 215 Services and Daemons............................................. 216 Security........................................................ 217 Summary....................................................... 217 Project #20: Examine Running Processes.................................... 218 Project #21: Create a Thread and Observe It................................. 220 Project #22: Examine Virtual Memory...................................... 222 Project #23: Try the Operating System API.................................. 224 Project #24: Observe System Calls........................................ 226 Project #25: Use glibc.................................................. 227 Project #26: View Loaded Kernel Modules.................................. 230 Project #27: Examine Storage Devices and Filesystems.......................... 230 Project #28: View Services.............................................. 231 11 THE INTERNET 233 Networking Terms Defined........................................... 233 The Internet Protocol Suite........................................... 235 Link Layer................................................ 238 Internet Layer.............................................. 239 Transport Layer............................................ 243 Application Layer........................................... 245 A Trip Through the Internet........................................... 246 Foundational Internet Capabilities..................................... 247 Dynamic Host Configuration Protocol............................. 247 Private IP Addresses and Network Address Translation................. 248 The Domain Name System.................................... 250 Networking Is Computing........................................... 252 Summary....................................................... 253 Project #29: Examine the Link Layer....................................... 254 Project #30: Examine the Internet Layer.................................... 255 Project #31: Examine Port Usage.......................................... 256 Project #32: Trace the Route to a Host on the Internet.......................... 258 Project #33: See Your Leased IP Address.................................... 258 Project #34: Is Your Device’s IP Public or Private?............................. 259 Project #35: Find Information in DNS...................................... 260 xiv   Contents in Detail 12 THE WORLD WIDE WEB 261 Overview of the World Wide Web..................................... 261 The Distributed Web......................................... 262 The Addressable Web....................................... 262 The Linked Web............................................ 264 The Protocols of the Web..................................... 264 The Searchable Web........................................ 267 The Languages of the Web.......................................... 268 Structuring the Web with HTML................................. 268 Styling the Web with CSS..................................... 271 Scripting the Web with JavaScript............................... 273 Structuring the Web’s Data with JSON and XML..................... 275 Web Browsers................................................... 277 Rendering a Page.......................................... 277 The User Agent String........................................ 279 Web Servers.................................................... 280 Summary....................................................... 282 Project #36: Examine HTTP Traffic......................................... 283 Project #37: Run Your Own Web Server.................................... 285 Project #38: Return HTML from Your Web Server.............................. 287 Project #39: Add CSS to Your Website...................................... 288 Project #40: Add JavaScript to Your Website................................. 289 13 MODERN COMPUTING 291 Apps.......................................................... 292 Native Apps.............................................. 292 Web Apps............................................... 294 Virtualization and Emulation.......................................... 295 Virtualization.............................................. 295 Emulation................................................ 297 Cloud Computing................................................. 298 The History of Remote Computing............................... 298 The Categories of Cloud Computing............................. 299 The Deep Web and Dark Web........................................ 301 Bitcoin......................................................... 302 Bitcoin Basics............................................. 302 Bitcoin Wallets............................................. 303 Bitcoin Transactions......................................... 304 Bitcoin Mining............................................. 305 Virtual Reality and Augmented Reality................................... 306 The Internet of Things............................................... 308 Summary....................................................... 309 Project #41: Use Python to Control a Vending Machine Circuit..................... 311 Contents in Detail   xv A ANSWERS TO EXERCISES 319 B RESOURCES 333 Buying Electronic Components for the Projects............................. 333 7400 Part Numbers......................................... 334 Shopping................................................ 335 Powering Digital Circuits............................................ 336 USB Charger.............................................. 336 Breadboard Power Supply.................................... 337 Power from a Raspberry Pi.................................... 338 AA Batteries.............................................. 339 Troubleshooting Circuits............................................. 340 Raspberry Pi..................................................... 341 Why Raspberry Pi.......................................... 341 Parts Needed............................................. 342 Setting Up a Raspberry Pi..................................... 343 Using Raspberry Pi OS....................................... 344 Working with Files and Folders................................. 346 INDEX 351 xvi   Contents in Detail  ACKNOWLEDGMENTS An enormous thank you to my wife, Suzy, who acted as my informal editor, providing me with invaluable feedback. She scrutinized every word and every concept through multiple drafts of this book, helping me refine my ideas and express them clearly. She encouraged and supported me in this endeavor from concept to completion. Thanks to my teenage daughters, Ava and Ivy, who read my early drafts and helped me see my writing through the eyes of younger learners. They helped me avoid confusing language and showed me where I needed to spend more time explaining things. I want to express gratitude to my parents, Russell and Debby Justice, who always believed in me, and who provided me with ample opportunities to learn. My love of the written word comes from my Mom, and my engi- neering mindset comes from my Dad. Thank you to the entire team at No Starch Press, especially Alex Freed and Katrina Taylor, and thanks to my copyeditor, Rebecca Rider. This was my first time authoring a book, and the editors at No Starch patiently guided me through the process. They saw opportunities for improvement that I hadn’t considered, and they helped me communicate my ideas clearly. I’ve gained a new appreciation for the value that a publishing team can bring. I’m thankful for this book’s technical reviewers, John Hewes, Bryan Wilhelm, and Bill Young, who diligently examined the details of my writing.  Their input resulted in content that’s more accurate and more com- plete. They each brought a unique perspective and shared their valuable expertise. Thanks to all the people at Microsoft who mentored me and collabo- rated with me throughout the years. I’ve been fortunate to work with some incredibly talented, intelligent, and knowledgeable folks—there’s too many of you to list! I’m only able to write a book like this because some great people at Microsoft took the time to share their knowledge with me. xviii   Acknoweldgements  INTRODUCTION Are you curious about how computers work? Gaining a broad understanding of computing is often a long and winding path. The problem isn’t a lack of documentation. A quick search online shows that there are many, many books and websites devoted to explaining computing. Programming, computer science, electronics, operat- ing systems... a wealth of information is out there. This is a good thing, but it can be daunting. Where should you begin? How does one topic connect to another? This book was written to give you an entry point for learning about key concepts of computing and how these concepts fit together.  When I worked as an engineering manager, I regularly interviewed people for software development jobs. I spoke to many candidates who knew how to write code, but a significant number of them didn’t seem to know how comput- ers really work. They knew how to make a computer do their bidding, but they didn’t understand what was going on behind the scenes. Reflecting on those interviews, and on memories of my own struggles in trying to learn about com- puters, led me to write this book. My goal is to present the fundamentals of computing in an accessible, hands-­on way that makes abstract concepts more real. This book doesn’t go deep on every topic presented, but instead, it presents the foundational concepts of computing and connects the dots between those concepts. I want you to be able to construct a mental picture of how computing works, enabling you to then dig deeper on the topics that interest you. Computing is everywhere, and as our society depends more and more on technology, we need individuals who broadly understand computing. My hope is that this book will help you gain that broad perspective. Who Is This Book For? This book is for anyone who wants to understand how computers work. You don’t need to have any prior knowledge of the topics covered—we begin with the basics. On the other hand, if you already have a back- ground in programming or electronics, this book can help you expand your knowledge in other areas. The book is written for the self-­motivated learner, someone who is comfortable with basic math and science, and who is already familiar with using computers and smartphones, but who still has questions about how they work. Teachers should find the content useful too; I believe the projects are a good fit for the classroom. About This Book This book looks at computing as a technology stack. A modern comput- ing device, such as a smartphone, is composed of layers of technology. At the bottom of the stack we have hardware, and at the top of the stack we have apps, with multiple technology layers in between. The beauty of the layered model is that each layer benefits from all the capabilities of the lower levels, but any given layer only needs to build upon the layer directly below it. After covering some foundational concepts, we’ll progress through the technology stack from the bottom up, starting with electrical circuits and working our way up to the technologies that power the web and apps. Here’s what we’ll cover in each chapter: Chapter 1: Computing Concepts Covers foundational ideas, such as understanding analog versus digital, the binary number system, and SI prefixes Chapter 2: Binary in Action Looks at how binary can be used to represent both data and logical states, and includes an introduction to logical operators xx Introduction  Chapter 3: Electrical Circuits Explains basic concepts of electricity and electrical circuits, including voltage, current, and resistance Chapter 4: Digital Circuits Introduces transistors and logic gates, and brings together concepts from Chapters 2 and 3 Chapter 5: Math with Digital Circuits Shows how addition can be performed with digital circuits and covers more details about how num- bers are represented in computers Chapter 6: Memory and Clock Signals Introduces memory devices and sequential circuits, and demonstrates synchronization through clock signals Chapter 7: Computer Hardware Covers the major parts of a com- puter: processor, memory, and input/output Chapter 8: Machine Code and Assembly Language Presents low-­level machine code that processors execute, and covers assembly language, the human-­readable form of machine code Chapter 9: High-­L evel Programming Introduces programming lan- guages that are independent from specific processors, and includes example code in C and Python Chapter 10: Operating Systems Covers families of operating systems and the core capabilities of operating systems Chapter 11: The Internet Looks at how the internet works, including the common suite of network protocols it uses Chapter 12: The World Wide Web Explains how the web works, and looks at its core technologies: HTTP, HTML, CSS, and JavaScript Chapter 13: Modern Computing Provides overviews of a handful of modern computing topics, such as apps, virtualization, and cloud services As you read through this book, you’ll come across circuit diagrams and source code used to illustrate concepts. These are intended as teach- ing tools, favoring clarity over performance, security, and other factors that engineers consider when designing hardware or software. In other words, the circuits and code in this book can help you learn how computers work, but they aren’t necessarily examples of the best way to do things. Similarly, the book’s technical explanations favor simplicity over completeness. I sometimes gloss over certain details to avoid getting mired in complexity. About Exercises and Projects Throughout the chapters you’ll find exercises and hands-on projects. The exercises are problems for you to work out mentally or with pencil and paper. The projects go beyond mental exercises and often involve building a circuit or programming a computer. You’ll need to acquire some hardware to perform the projects (you can find a list of needed components in Appendix B). I’ve included these proj- ects because I believe that the best way to learn is to try things yourself, and I encourage you to complete the projects if you want to get the most out of Introduction xxi  this book. That said, I’ve presented the chapter material in a way that allows you to still follow along, even if you don’t build a single circuit or enter one line of code. You can find the answers to exercises in Appendix A, and the details for each project are found at the end of the corresponding chapter. Appendix B contains information to help you get started with projects, and the project text points you there when needed. A copy of the source code used in the projects is available at https:// www.howcomputersreallywork.com/code/. You can also visit this book’s page at https://nostarch.com/how-computers-really-work/ where we will provide updates. My Computing Journey My fascination with computers probably began with the video games I played as a kid. When I visited my grandparents, I’d spend hours playing Frogger, Pac-­Man, and Donkey Kong on my aunt’s Atari 2600. Later, when I was in fifth grade, my parents gave me a Nintendo Entertainment System for Christmas, and I was thrilled! While I loved playing Super Mario Bros. and Double Dragon, somewhere along the way, I began to wonder how video games and comput- ers worked. Unfortunately, my Nintendo game console didn’t provide me with many clues as to what was going on inside it. Around the same time, my family bought our first “real” computer, an Apple IIGS, opening new doors for me to explore exactly how these machines functioned. Fortunately, my middle school offered a class on BASIC program- ming of Apple II computers, and I soon learned that I couldn’t get enough of coding! I would write code at school, bring home a copy of my work on floppy disk, and continue working at home. Throughout middle school and high school, I learned more about programming, and I greatly enjoyed it. I also began to realize that although BASIC and other similar programming languages make it relatively easy to tell a computer what to do, they also hide many details of how computers work. I wanted to go deeper. In college I studied electrical engineering, and I began to understand electronics and digital circuits. I took classes on C programming and assem- bly language, and I finally got glimpses of how computers execute instruc- tions. The low-­level details of how computers work were beginning to make sense. While in college, I also started learning about this new thing called the World Wide Web; I even crafted my very own web page (this seemed like a big deal at the time)! I began programming Windows applications, and I was introduced to Unix and Linux. These topics sometimes seemed far removed from the hardware-­specific details of digital circuits and assem- bly language, and I was curious to understand how it all fit together. After college I was fortunate to get a job at Microsoft. In my 17 years there, I worked in various software engineering roles, from debugging the Windows kernel to developing web applications. These experiences helped me gain a broader and deeper understanding of computers. I worked with many incredibly smart and knowledgeable people, and I learned that there’s always more to learn about computing. Understanding how computers work has been a lifelong journey for me, and I hope to pass on some of what I’ve learned to you through this book. xxii Introduction  1 COMPUTING CONCEP TS Computers are everywhere now: in our homes, our schools, our offices—you might find a computer in your pocket, on your wrist, or even in your refrigerator. It’s easier than ever to find and use computers, but few people today really understand how computers work. This isn’t sur- prising, since learning the complexities of computing can be overwhelming. The goal of this book is to lay out the foundational principles of computing in a way that anyone with curiosity, and a bit of a technical bent, can follow. Before we dig into the nuts and bolts of how computers work, let’s take some time to get familiar with some major concepts of computing.  In this chapter we’ll begin by discussing the definition of a computer. From there, we’ll cover the differences between analog and digital data and then explore number systems and the terminology used to describe digital data. Defining a Computer Let’s start with a basic question: what is a computer? When people hear the word computer, most think of a laptop or desktop, sometimes referred to as a personal computer or PC. That is one class of device that this book cov- ers, but let’s think a bit more broadly. Consider smartphones. Smartphones are certainly computers; they perform the same types of operations as PCs. In fact, for many people today, a smartphone is their primary computing device. Most computer users today also rely on the internet, which is pow- ered by servers—another type of computer. Every time you visit a website or use an app that connects to the internet, you’re interacting with one or more servers connected to a global network. Video game consoles, fitness trackers, smart watches, smart televisions... all of these are computers! A computer is any electronic device that can be programmed to carry out a set of logical instructions. With that definition in mind, it becomes clear that many modern devices are in fact computers! E X E RCISE 1-1: FIND THE COMPU TE RS IN YOUR HOME Take a moment and see how many computers you can identify in your home. When I did this exercise with my family, we quickly found about 30 devices! Analog and Digital You’ve probably heard a computer described as a digital device. This is in contrast to an analog device, such as a mechanical clock. But what do these two terms really mean? Understanding the differences between analog and digital is foundational to understanding computing, so let’s take a closer look at these two concepts. The Analog Approach Look around you. Pick an object. Ask yourself: What color is it? What size is it? How much does it weigh? By answering these questions, you’re describ- ing the attributes, or data, of that object. Now, pick a different object and answer the same questions. If you repeat this process for even more objects, you’ll find that for each question, the potential answers are numerous. You might pick up a red object, a yellow object, or a blue object. Or the object 2 Chapter 1 could be a mix of the primary colors. This type of variation does not only apply to color. For a given property, the variations found across the objects in our world are potentially infinite. It’s one thing to describe an object verbally, but let’s say you want to measure one of its attributes more precisely. If you wanted to measure an object’s weight, for example, you could put it on a scale. The scale, respond- ing to the weight placed upon it, would move a needle along a numbered line, stopping when it reaches a position that corresponds to the weight. Read the number from the scale and you have the object’s weight. This kind of measurement is common, but let’s think a little more about how we’re measuring this data. The position of the needle on the scale isn’t actually the weight; it’s a representation of the weight. The numbered line that the needle points to provides a means for us to easily convert between the needle’s position, representing a weight, and the numeric value of that weight. In other words, though the weight is an attribute of the object, here we can understand that attribute through something else: the position of the needle along the line. The needle’s position changes proportionally in response to the weight placed on the scale. Thus, the scale is working as an analogy where we understand the weight of the object through the needle’s position on the line. This is why we call this method of measuring the ana- log approach. Another example of an analog measuring tool is a mercury thermom- eter. Mercury’s volume increases with temperature. Thermometer manufac- turers utilize this property by placing mercury in a glass tube with markings that correspond to the expected volume of the mercury at various tem- peratures. Thus, the position of mercury in the tube serves as a representa- tion of temperature. Notice that for both of these examples (a scale and a thermometer), when we make a measurement, we can use markings on the instrument to convert a position to a specific numeric value. But the value we read from the instrument is just an approximation. The true position of the needle or mercury can be anywhere within the range of the instrument, and we round up or down to the nearest marked value. So although it may seem that these tools can produce only a finite set of measurements, that’s a limitation imposed by the conversion to a number, not by the analogy itself. Throughout most of human history, humans have measured things using an analog approach. But people don’t only use analog approaches for measurement. They’ve also devised clever ways to store data in an analog fashion. A phonograph record uses a modulated groove as an analog rep- resentation of audio that was recorded. The groove’s shape changes along its path in a way that corresponds to changes in the shape of the audio waveform over time. The groove isn’t the audio itself, but it’s an analogy of the original sound’s waveform. Film-­based cameras do something similar by briefly exposing film to light from a camera lens, leading to a chemical change in the film. The chemical properties of the film are not the image itself, but a representation of the captured image, an analogy of the image. Computing Concepts 3  Going Digital What does all this have to do with computing? It turns out that all those analog representations of data are hard for computers to deal with. The types of analog systems used are so different and variable that creating a common computing device that can understand all of them is nearly impos- sible. For example, creating a machine that can measure the volume of mercury is a very different task than creating a machine that can read the grooves on a vinyl disc. Additionally, computers require highly reliable and accurate representations of certain types of data, such as numeric data sets and software programs. Analog representations of data can be difficult to measure precisely, tend to decay over time, and lose fidelity when copied. Computers need a way to represent all types of data in a format that can be accurately processed, stored, and copied. If we don’t want to represent data as something with potentially infinitely varying analog values, what can we do? We can use a digital approach instead. A digital system represents data as a sequence of symbols, where each symbol is one of a limited set of values. Now, that description may sound a bit formal and a bit confusing, so rather than go deep on the theory of digital systems, I’ll explain what this means in practice. In almost all of today’s computers, data is represented with combinations of two symbols: 0 and 1. That’s it. Although a digital system could use more than two symbols, adding more symbols would increase the complexity and cost of the system. A set of only two symbols allows for simplified hardware and improved reliability. All data in most modern computing devices is represented as a sequence of 0s and 1s. From this point forward in this book, when I talk about digital computers, you can assume that I am talking about systems that only deal with 0s and 1s and not some other set of symbols. Nice and simple! It’s a point worth repeating: everything on your computer is stored as 0s and 1s. The last photo you took on your smartphone? Your device stored the photo as a sequence of 0s and 1s. The song you streamed from the internet? 0s and 1s. The document you wrote on your computer? 0s and 1s. The app you installed? It was a bunch of 0s and 1s. The website you visited? 0s and 1s. It may sound limiting to say that we can only use 0 and 1 to represent the infinite values found in nature. How can a musical recording or a detailed photograph be distilled down to 0s and 1s? Many find it counterintuitive that such a limited “vocabulary” can be used to express complex ideas. The key here is that digital systems use a sequence of 0s and 1s. A digital photograph, for example, usually consists of millions of 0s and 1s. So what exactly are these 0s and 1s? You may see other terms used to describe these 0s and 1s: false and true, off and on, low and high, and so forth. This is because the computer doesn’t literally store the number 0 or 1. It stores a sequence of entries where each entry in the sequence can have only two possible states. Each entry is like a light switch that is either on or off. In practice, these sequences of 1s and 0s are stored in various ways. On a CD or DVD, the 0s and 1s are stored on the disc as bumps (0) or flat spaces (1). On a flash drive, the 1s and 0s are stored as electrical charges. A hard disk drive stores the 0s and 1s using magnetization. As you’ll see in Chapter 4, digital circuits represent 0s and 1s using voltage levels. 4 Chapter 1  Before we move on, one final note on the term analog—it’s often used to simply mean “not digital.” For example, engineers may speak of an “ana- log signal,” meaning a signal that varies continuously and doesn’t align to digital values. In other words, it’s a non-­digital signal but doesn’t necessarily represent an analogy of something else. So, when you see the term analog, consider that it might not always mean what you think. Number Systems So far, we’ve established that computers are digital machines that deal with 0s and 1s. For many people, this concept seems strange; they’re used to having 0 through 9 at their disposal when representing numbers. If we constrain ourselves to only two symbols, rather than ten, how should we represent large numbers? To answer that question, let’s back up and review an elementary school math topic: number systems. Decimal Numbers We typically write numbers using something called decimal place-­value nota- tion. Let’s break that down. Place-­value notation (or positional notation) means that each position in a written number represents a different order of mag- nitude; decimal, or base 10, means that the orders of magnitude are factors of 10, and each place can have one of ten different symbols, 0 through 9. Look at the example of place-­value notation in Figure 1-1. 2 7 5 Hundreds Tens Ones place place place Figure 1-1: Two hundred seventy-­five represented in decimal place-­value notation In Figure 1-1, the number two hundred seventy-­five is written in decimal notation as 275. The 5 is in the ones place, meaning its value is 5 × 1 = 5. The 7 is in the tens place, meaning its value is 7 × 10 = 70. The 2 is in the hundreds place, meaning its value is 2 × 100 = 200. The total value is the sum of all the places: 5 + 70 + 200 = 275. Easy, right? You’ve probably understood this since first grade. But let’s examine this a bit closer. Why is the rightmost place the ones place? And why is the next place the tens place, and so on? It’s because we are work- ing in decimal, or base 10, and therefore each place is a power of ten—in other words, 10 multiplied by itself a certain number of times. As seen in Figure 1-2, the rightmost place is 10 raised to 0, which is 1, because any number raised to 0 is 1. The next place is 10 raised to 1, which is 10, and the next place is 10 raised to 2 (10 × 10), which is 100. Computing Concepts 5  2 7 5 102 101 100 10 ×10 10 1 Figure 1-2: In decimal place-­value notation, each place is a power of ten. If we needed to represent a number larger than 999 in decimal, we’d add another place to the left, the thousands place, and its weight would be equal to 10 raised to 3 (10 × 10 × 10), which is 1,000. This pattern continues so that we can represent any large whole number by adding more places as needed. We’ve established why the various places have certain weights, but let’s keep digging. Why does each place use the symbols 0 through 9? When working in decimal, we can only have ten symbols, because by definition each place can only represent ten different values. 0 through 9 are the sym- bols that are currently used, but really any set of ten unique symbols could be used, with each symbol corresponding to a certain numeric value. Most humans prefer decimal, base 10, as a number system. Some say this is because we have ten fingers and ten toes, but whatever the reason, in the modern world most people read, write, and think of numbers in decimal. Of course, that’s just a convention we’ve collectively chosen to represent numbers. As we covered earlier, that convention doesn’t apply to computers, which instead use only two symbols. Let’s see how we can apply the principles of the place-­value system while constraining ourselves to only two symbols. Binary Numbers The number system consisting of only two symbols is base 2, or binary. Binary is still a place-­value system, so the fundamental mechanics are the same as decimal, but there are a couple of changes. First, each place repre- sents a power of 2, rather than a power of 10. Second, each place can only have one of two symbols, rather than ten. Those two symbols are 0 and 1. Figure 1-3 has an example of how we’d represent a number using binary. 1 0 1 Fours Twos Ones place place place 22 21 20 2×2=4 2 1 Figure 1-3: Five decimal represented in binary place-­value notation 6 Chapter 1  In Figure 1-3, we have a binary number: 101. That may look like one hundred and one to you, but when dealing in binary, this is actually a repre- sentation of five! If you wish to verbally say it, “one zero one binary” would be a good way to communicate what is written. Just like in decimal, each place has a weight equal to the base raised to various powers. Since we are in base 2, the rightmost place is 2 raised to 0, which is 1. The next place is 2 raised to 1, which is 2, and the next place is 2 raised to 2 (2 × 2), which is 4. Also, just like in decimal, to get the total value, we multiply the symbol in each place by the place-­value weight and sum the results. So, starting from the right, we have (1 × 1) + (0 × 2) + (1 × 4) = 5. Now you can try converting from binary to decimal yourself. E X E RCISE 1-2: BIN A RY TO DECIM A L Convert these numbers, represented in binary, to their decimal equivalents. 10 (binary) = ______ (decimal) 111 (binary) = ______ (decimal) 1010 (binary) = ______ (decimal) You can check your answers in Appendix A. Did you get them right? The last one might have been a bit tricky, since it introduced another place to the left, the eights place. Now, try going the other way around, from deci- mal to binary. E X E RCISE 1-3: DECIM A L TO BIN A RY Convert these numbers, represented in decimal, to their binary equivalents. 3 (decimal) = ______ (binary) 8 (decimal) = ______ (binary) 14 (decimal) = ______ (binary) I hope you got those correct too! Right away, you can see that dealing with both decimal and binary at the same time can be confusing, since a number like 10 represents ten in decimal or two in binary. From this point forward in the book, if there’s a chance of confusion, binary numbers will be written with a 0b prefix. I’ve chosen the 0b prefix because several pro- gramming languages use this approach. The leading 0 (zero) character indicates a numeric value and the b is short for binary. As an example, 0b10 represents two in binary, whereas 10, with no prefix, means ten in decimal. Computing Concepts 7  Bits and Bytes A single place or symbol in a decimal number is called a digit. A decimal number like 1,247 is a four-­digit number. Similarly, a single place or symbol in a binary number is called a bit (a binary digit). Each bit can either be 0 or 1. A binary number like 0b110 is a 3-bit number. A single bit cannot convey much information; it’s either off or on, 0 or 1. We need a sequence of bits to represent anything more complex. To make these sequences of bits easier to manage, computers group bits together in sets of eight, called bytes. Here are some examples of bits and bytes (leaving off the 0b prefix since they are all binary): 1 That’s a bit. 0 That is also a bit. 11001110 That’s a byte, or 8 bits. 00111000 That’s also a byte! 10100101 Yet another byte. 0011100010100101 That’s two bytes, or 16 bits. NOTE Fun fact: A 4-bit number, half a byte, is sometimes called a nibble (sometimes spelled nybble or nyble). So how much data can we store in a byte? Another way to think about this question is how many unique combinations of 0s and 1s can we make with our 8 bits? Before we answer that question, let me illustrate with only 4 bits, as it’ll be easier to visualize. In Table 1-1, I’ve listed all the possible combination of 0s and 1s in a 4-bit number. I’ve also included the corresponding decimal representation of that number. Table 1-1: All Possible Values of a 4-bit Number Binary Decimal 0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7 1000 8 1001 9 1010 10 8 Chapter 1  Binary Decimal 1011 11 1100 12 1101 13 1110 14 1111 15 As you can see in Table 1-1, we can represent 16 unique combinations of 0s and 1s in a 4-bit number, ranging in decimal value from 0 to 15. Seeing the list of combinations of bits helps to illustrate this, but we could have figured this out in a couple of ways without enumerating every pos- sible combination. We could determine the largest possible number that 4 bits can repre- sent by setting all the bits to one, giving us 0b1111. That is 15 in decimal; if we add 1 to account for representing 0, then we come to our total of 16. Another shortcut is to raise 2 to the number of bits, 4 in this case, which gives us 24 = 2 × 2 × 2 × 2 = 16 total combinations of 0s and 1s. Looking at 4 bits is a good start, but previously we were talking about bytes, which contain 8 bits. Using the preceding approach, we could list out all combinations of 0s and 1s, but let’s skip that step and go straight to a shortcut. Raise 2 to the power of 8 and you get 256, so that’s the number of unique combinations of bits in a byte. Now we know that a 4-bit number allows for 16 combinations of 0s and 1s, and a byte allows for 256 combinations. What does that have to do with computing? Let’s say that a computer game has 12 levels; the game could easily store the current level number in only 4 bits. On the other hand, if the game has 99 levels, 4 bits won’t be enough... only 16 levels could be represented! A byte, on the other hand, would handle that 99-level require- ment just fine. Computer engineers sometimes need to consider how many bits or bytes will be needed for storage of data. Prefixes Representing complex data types takes a large number of bits. Something as simple as the number 99 won’t require more than a byte; a video in a digital format, on the other hand, can require billions of bits. To more eas- ily communicate the size of data, we use prefixes like giga- and mega-. The International System of Units (SI), also known as the metric system, defines a set of standard prefixes. These prefixes are used to describe anything that can be quantified, not just bits. We’ll see them again in upcoming chapters dealing with electrical circuits. Table 1-2 lists some of the common SI pre- fixes and their meanings. Computing Concepts 9  Table 1-2: Common SI Prefixes Prefix name Prefix symbol Value Base 10 English word 12 tera T 1,000,000,000,000 10 trillion 9 giga G 1,000,000,000 10 billion mega M 1,000,000 106 million 3 kilo k 1,000 10 thousand -2 centi c 0.01 10 hundredth milli m 0.001 10 -3 thousandth -6 micro µ 0.000001 10 millionth -9 nano n 0.000000001 10 billionth pico p 0.000000000001 10 -12 trillionth With these prefixes, if we want to say “3 billion bytes,” we can use the shorthand 3GB. Or if we want to represent 4 thousand bits, we can say 4kb. Note the uppercase B for byte and lowercase b for bit. You’ll find that this convention is commonly used to represent quantities of bits and bytes. Unfortunately, it’s also often technically incorrect. Here’s why: when dealing with bytes, most software is actually working in base 2, not base 10. If your computer tells you that a file is 1MB in size, it is actually 1,048,576 bytes! That is approximately one million, but not quite. Seems like an odd number, doesn’t it? That’s because we are looking at it in decimal. In binary, that same number is expressed as 0b100000000000000000000. It’s a power of two, specifically 220. Table 1-3 shows how to interpret the SI prefixes when dealing with bytes. Table 1-3: SI Prefix Meaning When Applied to Bytes Prefix name Prefix symbol Value Base 2 tera T 1,099,511,627,776 240 giga G 1,073,741,824 230 mega M 1,048,576 220 kilo k 1,024 210 Another point of confusion with bits and bytes relates to network transfer rates. Internet service providers usually advertise in bits per second, base 10. So, if you get 50 megabits per second from your internet connection, that means you can only transfer about 6 megabytes per second. That is, 50,000,000 bits per second divided by 8 bits per byte gives us 6,250,000 bytes per second. Divide 6,250,000 by 220 and we get about 6 megabytes per second. 10 Chapter 1  SI PRE FI X E S FOR BIN A RY DATA To address the confusion caused by multiple meanings of prefixes, a new set of prefixes was introduced in 2002 (in a standard called IEEE 1541) to be used for binary scenarios. When dealing with powers of 2, kibi- is to be used instead of kilo-, mebi- is to be used instead of mega-, and so on. These new prefixes correspond to base 2 values and are intended to be used in scenarios where the old prefixes were previously being used incorrectly. For example, since kilobyte might be interpreted as 1,000 or 1,024 bytes, this standard recommends that kibibyte be used to mean 1,024 bytes, while kilo- retains its original meaning so that a kilobyte is equal to 1,000 bytes. This seems like a good idea, but at the time of this writing, these sym- bols haven’t been widely adopted. Table 1-4 lists the new prefixes and their meanings. Table 1-4: IEEE 1541-2002 Prefixes for Binary Data Prefix name Prefix symbol Value Base 2 tebi Ti 1,099,511,627,776 240 gibi Gi 1,073,741,824 230 mebi Mi 1,048,576 220 kibi Ki 1,024 210 This distinction is important because in practice, most software that dis- plays the size of files uses the old SI prefix but calculates size using base 2. In other words, if your device says a file’s size is 1KB, it means 1,024 bytes. On the other hand, manufacturers of storage devices tend to advertise the capacity of their devices using base 10. This means that a hard drive that is advertised as 1TB probably holds 1 trillion bytes, but if you connect that device to a computer, the computer will show the size as about 931GB (1 trillion divided by 230). Given the lack of standard adoption of the new prefixes, in this book, I will continue to use the old SI prefixes. Hexadecimal Before we leave the topic of thinking in binary, I’ll cover one more number system: hexadecimal. Quickly reviewing, our “normal” number system is deci- mal, or base 10. Computers use binary, or base 2. Hexadecimal is base 16! Given what you’ve already learned in this chapter, you probably know what that means. Hexadecimal, or just hex for short, is a place-­value system where each place represents a power of 16, and each place can be one of 16 symbols. Computing Concepts 11  As in all place-­value systems, the rightmost place will still be the ones place. The next place to the left will be the sixteens place, then the 256s (16 × 16) place, then the 4,096s (16 × 16 × 16) place, and so on. Simple enough. But what about the other requirement that each place can be one of 16 symbols? We usually have ten symbols to use to represent numbers, 0 through 9. We need to add six more symbols to represent the other values. We could pick some random symbols like & @ #, but these symbols have no obvious order. Instead, the standard is to use A, B, C, D, E, and F (either uppercase or lowercase is fine!). In this scheme, A represents ten, B repre- sents eleven, and so on, up to F, which represents fifteen. That makes sense; we need symbols that represent zero through one less than the base. So our extra symbols are A through F. It’s standard practice to use the prefix 0x to indicate hexadecimal, when needed for clarity. Table 1-5 lists each of the 16 hexadecimal symbols, along with their decimal and binary equivalents. Table 1-5: Hexadecimal Symbols Hexadecimal Decimal Binary (4-bit) 0 0 0000 1 1 0001 2 2 0010 3 3 0011 4 4 0100 5 5 0101 6 6 0110 7 7 0111 8 8 1000 9 9 1001 A 10 1010 B 11 1011 C 12 1100 D 13 1101 E 14 1110 F 15 1111 What happens when you need to count higher than 15 decimal or 0xF? Just like in decimal, we add another place. After 0xF comes 0x10, which is 16 decimal. Then 0x11, 0x12, 0x13, and so on. Now take a look at Figure 1-4, where we see a larger hexadecimal number, 0x1A5. 12 Chapter 1  1 A 5 256s Sixteens Ones place place place 162 161 160 16 × 16 = 256 16 1 Figure 1-4: Hexadecimal number 0x1A5 broken out by place value In Figure 1-4 we have the number 0x1A5 in hexadecimal. What’s the value of this number in decimal? The rightmost place is worth 5. The next place has a weight of 16, and there’s an A there, which is 10 in decimal, so the middle place is worth 16 × 10 = 160. The leftmost place has a weight of 256, and there’s a 1 in that place, so that place is worth 256. The total value then is 5 + 160 + 256 = 421 in decimal. Just to reinforce the point, this example shows how the new symbols, like A, have a different value depending on the place in which they appear. 0xA is 10 decimal, but 0xA0 is 160 in decimal, because the A appears in the sixteens place. At this point you may be saying to yourself “great, but what use is this?” I’m glad you asked. Computers don’t use hexadecimal, and neither do most people. And yet, hexadecimal is very useful for people who need to work in binary. Using hexadecimal helps overcome two common difficulties with work- ing in binary. First, most people are terrible at reading long sequences of 0s and 1s. After a while the bits all run together. Dealing with 16 or more bits is tedious and error-­prone for humans. The second problem is that although people are good at working in decimal, converting between deci- mal and binary isn’t easy. It’s tough for most people to look at a decimal number and quickly tell which bits would be 1 or 0 if that number were rep- resented in binary. But with hexadecimal, conversions to binary are much more straightforward. Table 1-6 provides a couple of examples of 16-bit binary numbers and their corresponding hexadecimal and decimal repre- sentations. Note that I’ve added spaces to the binary values for clarity. Table 1-6: Examples of 16-bit Binary Numbers as Decimal and Hexadecimal Example 1 Example 2 Binary 1111 0000 0000 1111 1000 1000 1000 0001 Hexadecimal F00F 8881 Decimal 61,455 34,945 Computing Concepts 13  Consider Example 1 in Table 1-6. In binary, there’s a clear sequence: the first four bits are 1, the next eight bits are 0, and the last four bits are 1. In decimal, this sequence is obscured. It isn’t clear at all from looking at 61,455 which bits might be set to 0 or 1. Hexadecimal, on the other hand, mirrors the sequence in binary. The first hex symbol is F (which is 1111 in binary), the next two hex symbols are 0, and the final hex symbol is F. Continuing to Example 2, the first three sets of four bits are all 1000 and the final set of four bits is 0001. That’s easy to see in binary, but rather hard to see in decimal. Hexadecimal provides a clearer picture, with the hexadecimal symbol of 8 corresponding to 1000 in binary and the hexa- decimal symbol of 1 corresponding to, well, 1! I hope you are seeing a pattern emerge: every four bits in binary cor- respond to one symbol in hexadecimal. If you remember, four bits is half a byte (or a nibble). Therefore, a byte can be easily represented with two hexadecimal symbols. A 16-bit number can be represented with four hex symbols, a 32-bit number with eight hex symbols, and so on. Let’s take the 32-bit number in Figure 1-5 as an example. 8A52FF00 1000 1010 0101 0010 1111 1111 0000 0000 Figure 1-5: Each hexadecimal character maps to 4 bits In Figure 1-5 we can digest this rather long number one half-­byte at a time, something that isn’t possible using a decimal representation of the same number (2,320,695,040). Because it’s relatively easy to move between binary and hex, many engi- neers will often use the two in tandem, converting to decimal numbers only when necessary. I’ll use hexadecimal later in this book where it makes sense. Try converting from binary to hexadecimal without going through the intermediate step of converting to decimal. E X E RCISE 1- 4: BIN A RY TO HE X A DECIM A L Convert these numbers, represented in binary, to their hexadecimal equiva- lents. Don’t convert to decimal if you can help it! The goal is to move directly from binary to hexadecimal. 10 (binary) = ______ (hexadecimal) 11110000 (binary) = ______ (hexadecimal) You can check your answers in Appendix A. 14 Chapter 1  Once you have the hang of binary to hexadecimal, try going the other way, from hex to binary. E X E RCISE 1-5: HE X A DECIM A L TO BIN A RY Convert these numbers, represented in hexadecimal, to their binary equiva- lents. Don’t convert to decimal if you can help it! The goal is to move directly from hexadecimal to binary. 1A (hexadecimal) = _____ (binary) C3A0 (hexadecimal) = ______ (binary) You can check your answers in Appendix A. Summary In this chapter, we covered some of the foundational concepts of com- puting. You learned that a computer is any electronic device that can be programmed to carry out a set of logical instructions. You then saw that modern computers are digital devices rather than analog devices, and you learned the difference between the two: analog systems are those that use widely varying values to represent data, whereas digital systems represent data as a sequence of symbols. After that, we explored how modern digital computers rely on only two symbols, 0 and 1, and learned about a number system consisting of only two symbols, base 2, or binary. We covered bits, bytes, and the standard SI prefixes (giga-, mega-, kilo-, and so on) you can use to more easily describe the size of data. Lastly, you learned how hexa- decimal is useful for people who need to work in binary. In the next chapter we’ll look more closely at how binary is used in digi- tal systems. We’ll take a look at how binary can be used to represent various types of data, and we’ll see how binary logic works. Computing Concepts 15  2 BIN A RY IN AC TION In the previous chapter we defined a computer as an electronic device that can be programmed to carry out a set of logical instructions. We then learned at a high level how everything in a computer, from the data it uses to the instructions it carries out, is stored in binary, 0s and 1s. In this chapter, I shed some light on how exactly 0s and 1s can be used to represent nearly any kind of data. We also cover how binary lends itself to logical operations.  Representing Data Digitally So far, we’ve focused on storing numbers in binary. More specifically, we covered how to store the positive integers, sometimes called whole numbers, and zero. However, computers store all data as bits: negative numbers, frac- tional numbers, text, colors, images, audio, and video, to name a few. Let’s consider how various types of data might be represented using binary. Digital Text Let’s begin with text as our first example of how bits, 0s and 1s, can rep- resent something other than a number. In the context of computing, text means a collection of alphanumeric and related symbols, also called char- acters. Text is usually used to represent words, sentences, paragraphs, and so forth. Text does not include formatting (bold, italics). For the purposes of this discussion, let’s limit our character set to the English alphabet and related characters. In computer programming, the term string is also com- monly used to refer to a sequence of text characters. Keeping that definition of text in mind, what exactly do we need to represent? We need A through Z, uppercase and lowercase, meaning A is a different symbol than a. We also want punctuation marks like commas and periods. We need a way to represent spaces. We also need digits 0 through 9. The digit requirement can be confusing; here I’m talking about including the symbols or characters that are used to represent the numbers 0 through 9, which is a different thing than storing the numbers 0 through 9. If we add up all the unique symbols we need to represent, just described, we have around 100 characters. So, if we need to have a unique combination of bits to represent each character, how many bits do we need per character? A 6-bit number gives us 64 unique combinations, which isn’t quite enough. But a 7-bit number gives us 128 combinations, enough to represent the 100 or so characters we need. However, since computers usually work in bytes, it makes sense to just round up and use a full 8 bits, one byte, to represent each character. With a byte we can represent 256 unique characters. So how might we go about using 8 bits to represent each character? As you may expect, there’s already a standard way of representing text in binary, and we’ll get to that in a minute. But before we do that, it’s impor- tant to understand that we can make up any scheme we want to represent each character, as long as the software running on a computer knows about our scheme. That said, some schemes are better than others for represent- ing certain types of data. Software designers prefer schemes that make com- mon operations easy to perform. Imagine that you are responsible for creating your own system that represents each character as a set of bits. You might decide to assign 0b00000000 to represent character A, and 0b00000001 to represent character B, and so on. This process of translating data into a digital format is known as encoding; when you interpret that digital data, it’s known as decoding. 18 Chapter 2  E X E RCISE 2-1: CRE ATE YOUR OW N SYS TE M FOR RE PRE SE NTING TE X T Define a way to represent the uppercase letters A through D as 8-bit numbers, and then encode the word DAD into 24 bits using your system. There’s no sin- gle right answer to this; see Appendix A for an example answer. Bonus: show your encoded 24-bit number in hexadecimal too. ASCII Fortunately, we already have several standard ways to represent text digitally, so we don’t have to invent our own! American Standard Code for Information Interchange (ASCII) is a format that represents 128 characters using 7 bits per character, although each character is commonly stored using a full byte, 8 bits. Using 8 bits instead of 7 just means we have an extra leading bit, left as 0. ASCII handles the characters needed for English, and another standard, called Unicode, handles characters used in nearly all languages, English included. For now, let’s focus on ASCII to keep things simple. Table 2-1 shows the binary and hexadecimal values for a subset of ASCII characters. The first 32 characters aren’t shown; they are control codes such as carriage return and form feed, originally intended for controlling devices rather than storing text. E X E RCISE 2-2: E NCODE A ND DECODE A SCII Using Table 2-1, encode the following words to ASCII binary and hexadecimal, using a byte for each character. Remember that there are different values for uppercase and lowercase letters. Hello 5 cats Using Table 2-1, decode the following words. Each character is repre- sented as an 8-bit ASCII value with spaces added for clarity. 01000011 01101111 01100110 01100110 01100101 01100101 01010011 01101000 01101111 01110000 Using Table 2-1, decode the following word. Each character is repre- sented as an 8-bit hexadecimal value with spaces added for clarity. 43 6C 61 72 69 6E 65 74 Answers are in Appendix A. Binary in Action 19  Table 2-1: ASCII Characters 0x20 Through 0x7F Binary Hex Char Binary Hex Char Binary Hex Char 00100000 20 [Space] 01000000 40 @ 01100000 60 ` 00100001 21 ! 01000001 41 A 01100001 61 a 00100010 22 " 01000010 42 B 01100010 62 b 00100011 23 # 01000011 43 C 01100011 63 c 00100100 24 $ 01000100 44 D 01100100 64 d 00100101 25 % 01000101 45 E 01100101 65 e 00100110 26 & 01000110 46 F 01100110 66 f 00100111 27 ' 01000111 47 G 01100111 67 g 00101000 28 ( 01001000 48 H 01101000 68 h 00101001 29 ) 01001001 49 I 01101001 69 i 00101010 2A * 01001010 4A J 01101010 6A j 00101011 2B + 01001011 4B K 01101011 6B k 00101100 2C , 01001100 4C L 01101100 6C l 00101101 2D - 01001101 4D M 01101101 6D m 00101110 2E. 01001110 4E N 01101110 6E n 00101111 2F / 01001111 4F O 01101111 6F o 00110000 30 0 01010000 50 P 01110000 70 p 00110001 31 1 01010001 51 Q 01110001 71 q 00110010 32 2 01010010 52 R 01110010 72 r 00110011 33 3 01010011 53 S 01110011 73 s 00110100 34 4 01010100 54 T 01110100 74 t 00110101 35 5 01010101 55 U 01110101 75 u 00110110 36 6 01010110 56 V 01110110 76 v 00110111 37 7 01010111 57 W 01110111 77 w 00111000 38 8 01011000 58 X 01111000 78 x 00111001 39 9 01011001 59 Y 01111001 79 y 00111010 3A : 01011010 5A Z 01111010 7A z 00111011 3B ; 01011011 5B [ 01111011 7B { 00111100 3C < 01011100 5C \ 01111100 7C | 00111101 3D = 01011101 5D ] 01111101 7D } 00111110 3E > 01011110 5E ^ 01111110 7E ~ 00111111 3F ? 01011111 5F _ 01111111 7F [Delete] It’s fairly straightforward to represent text in a digital format. A system like ASCII maps each character, or symbol, to a unique sequence of bits. A computing device then interprets that sequence of bits and displays the appropriate symbol to the user. 20 Chapter 2 Digital Colors and Images Now that we’ve seen how to represent numbers and text in binary, let’s explore another type of data: color. Any computing device that has a color graphics display needs to have some system for describing colors. As you might expect, as with text, we already have standard ways of storing color data. We’ll get to them, but first let’s design our own system for digitally describing colors. Let’s limit our range of colors to black, white, and shades of gray. This limited set of colors is known as grayscale. Just like we did with text, let’s begin by deciding how many unique shades of gray we want to represent. Let’s keep it simple and go with black, white, dark gray, and light gray. That’s four total grayscale colors, so how many bits do we need to represent four colors? Only 2 bits are needed. A 2-bit number can represent four unique values, since 2 raised to the power of 2 is 4. E X E RCISE 2-3: CRE ATE YOUR OW N SYS TE M FOR RE PRE SE NTING GR AYSC A LE Define a way to digitally represent black, white, dark gray, and light gray. There’s no single right answer to this; see Appendix A for an example answer. Once you’ve designed a system for representing shades of gray in binary, you can build on that approach and create your own system for describing a simple grayscale image. An image is essentially an arrange- ment of colors on a two-­dimensional plane. Those colors are typically arranged in a grid composed of single-­color squares called pixels. Here’s a simple example in Figure 2-1. Figure 2-1: A simple image Binary in Action 21  The image in Figure 2-1 has a width of 4 pixels and a height of 4 pixels, giving it a total of 16 pixels. If you squint and use your imagination, you may see a white flower and a dark sky beyond. The image consists of only three colors: white, light gray, and dark gray. NOTE Figure 2-1 is composed of some really large pixels to illustrate a point. Modern televi- sions, computer monitors, and smartphone screens can also be thought of as a grid of pixels, but each pixel is very small. For example, a high definition display is typically 1920 pixels (width) by 1080 pixels (height), for a total of about 2 million pixels! As another example, digital photographs often contain more than 10 million pixels in a single image. E X E RCISE 2- 4: CRE ATE YOUR OW N A PPROACH FOR RE PRE SE NTING SIMPLE IM AGE S Part 1 Building upon your previous system for representing grayscale colors, design an approach for representing an image composed of those colors. If you want to simplify things, you can assume that the image will always be 4 pixels by 4 pixels, like the one in Figure 2-1. Part 2 Using your approach from part 1, write out a binary representation of the flower image in Figure 2-1. Part 3 Explain your approach for representing images to a friend. Then give your friend your binary