Chapter 3: Computing with Base-n Numbers

We are all accustomed to decimal (base-10) numbers. In this chapter, we will introduce numbers in other bases, describe arithmetic operations with those numbers, and convert numbers from one base to another. We will then move to binary digits (base-2), which are the foundation on which all computer operations are built, develop an approach to efficient arithmetic with them, and look at some of the core uses of binary, including Boolean algebra. Lastly, we will discuss hexadecimal (base-16) numbers and their uses in computer science. We will use Python code to do some computations such as converting decimal numbers to binary and hexadecimal and use Boolean operators to select and view data that satisfies a certain criterion.

In this chapter, we will be covering the following topics:

• Base-n numbers
• Converting between bases
• Binary numbers and their application
• Boolean algebra
• Hexadecimal numbers and their application

By the end of this chapter, you should be able to write numbers in different bases and convert numbers from one base to another. For example, 123 is a base-10 number that can be converted into other bases, depending on the need. You will also learn about the importance of binary and hexadecimal number systems along with their applications in computer science.

Important Note

Please navigate to the graphic bundle link to refer to the color images for this chapter.

Understanding base-n numbers

In this section, we will discuss how to write numbers in different bases with the help of some examples.

A base-n system uses n different symbols for writing numbers, as in 0, 1, 2, …, n – 1. This n is called the radix of the numbering system. Of course, the customary base-10, or decimal, numbers use the digits 0 through 9.

All base-n numbers make use of the positional system, like the one used by decimal numbers, which we will discuss in the next example.

Example – Decimal numbers

Let's think about what it means to write the decimal number 3214 with the usual positional system. It seems trivial, but it is important to realize what exactly a digit in each position in this number represents in order to understand the commonality between the base-10 system we all know and this new idea of a base-n system. The number is made up of a sum of three thousands (103), two hundreds (102), one ten (101), and four ones (100), which we can write as follows:

3214 = 3 ∙ 103 + 2 ∙ 102 + 1 ∙ 101 + 4 ∙ 100

To distinguish between numbers written in different radixes, the radix is written as a subscript after the number. For example, 3214 in base-6 form is written as (3214)6. If no radix is specified, it is assumed to be in decimal (base-10) form unless the context makes some other base clear. As we can see, this number represented by this sequence of digits in base-6 has a very different value than the same sequence of symbols in decimal.

There is an unlimited number of different base-n systems, as we could theoretically use any real number for n, but only certain systems have been used frequently in applications. Some of the most widely used ones are noted in the following table:

Figure 3.1 – Common base-n numbering systems

Note that when we have bases larger than 10, we can no longer simply use a subset of the digits 0 through 9. For example, the hexadecimal system, which is commonly used in a number of applications in computer science, needs 16 distinct symbols, so it uses 0 through 9 and also the letters A through F. These letters represent the equivalent of the decimal numbers 11 through 15. We will learn about the hexadecimal number system later in this chapter.

Definition – Base-n numbers

A non-negative integer number can be represented in base-n as follows:

(dkdk-1 ∙ ∙ ∙ d1d0)n,

Here, the digits d0 through dk are not multiplied, but just written side by side. The decimal value of this number is this:

dknk + dk-1nk-1 + ∙∙∙ + d1n1 + d0n0

Now that we have a definition of base-n numbers and we have seen some examples, we can think about what it means to convert between different bases.

Converting between bases

Now that we have the basic knowledge about base-n numbers, let's move on and see how these numbers transform between different bases. We can transform numbers in any base to base-10 and vice versa. In this section, we will show the conversion between different bases along with examples and Python code.

Converting base-n numbers to decimal numbers

Using the definition of base-n numbers given previously, we can convert the following numbers to base-10, or decimal, form. Several examples follow:

• (a)n = a ∙ n0 = a
• (ab)n = a ∙ n1 + b ∙ n0 = an + b
• (abc)n = a ∙ n2 + b ∙ n1 + c ∙ n0 = an2 + bn + c
• (abcd)n = a ∙ n3 + b ∙ n2 + c ∙ n1 + d ∙ n0 = an3 + bn2 + cn + d

We can apply this according to the number of digits we have.

Example – Decimal value of a base-6 number

Let's convert the number (3214)6 into decimal form for this example:

(3214)6 = 3 ∙ 63 + 2 ∙ 62 + 1 ∙ 61 + 4 ∙ 60 = 648 + 72 + 6 + 4 = 730

This is far from the decimal number 3214. We can see that the same number (here 3214) has a different value based on the base it is written in. The most-used base is base-10.

Base-n to decimal conversion

To convert a decimal number to a certain base n, we repeatedly divide the number at hand by n and keep track of the remainders as we proceed with the division. Let's illustrate this procedure with the help of an example.

Example – Decimal to base-2 (binary) conversion

Let's convert 357 into binary form.

We repeatedly divide 357 by 2 and keep track of the remainders. First, we divide 357 by 2 to get 178 with a remainder of 1, which we write on the right side of the following table. In the next row, we divide 178 by 2 to get 89 with no remainder (0). We continue this in each row until we are unable to do it anymore:

Figure 3.2 – Converting a decimal number to binary

Now that we have the divisions performed and the remainders noted down, we can follow the direction of the arrows to get our binary number, that is, (101100101)2. This method can be used to convert a decimal number to any non-decimal base (base-2 for this example).

Now that we know how to do the conversion, let's investigate why this method works. For our current example, in order to convert into base-2, we repeatedly divide by 2, and so the remainders can only be 0 (for even numbers) or 1 (for odd numbers). Hence, a base-2 number only uses 0 and 1 for its representation.

The same goes for numbers represented in other bases. For example, to convert a decimal number to base-7, we would repeatedly divide by 7, and so the possible remainders vary from 0 through 6, which are the digits for representing a base-7 number.

Let's do some more examples to make this clearer.

Example – Decimal to binary and hexadecimal conversions in Python

Let's use Python to convert a decimal number to binary and hexadecimal. When you run the code, it will prompt you to enter a number of your choice, which will then be converted into both binary and hexadecimal numbers:

# TypeConversion from decimal with base 10

# to hexadecimal form with base 16

# to binary form with the base 2

# Taking input from user - an integer with base 10

number = int(input("Enter a number with base 10 "))

# Converting the decimal number input by user to Hexadecimal

print("Hexadecimal form of " + str(number) + " is " +

  hex(number).lstrip("0x").rstrip("L"))

# Converting the decimal number input by user to Binary

print("Binary form of " + str(number) + " is " + bin(number).

  lstrip("0b").rstrip("L"))

The output, if the user inputs 12345, is as follows:

Enter a number with base 10

123456

Hexadecimal form of 123456 is 1e240

Binary form of 123456 is 11110001001000000

From the preceding example, we can see that the hexadecimal number system is shorter and therefore easier to work with as compared to the binary number system.

In this section, we learned about different number systems and how to convert numbers from one base to another.

Next, we will continue to discuss a few applications in computer science of binary (base-2) numbers and hexadecimal (base-16) numbers.

Binary numbers and their applications

In this section, we will learn about the binary number system in detail along with its applications and importance in computer science. In particular, we will consider a brief history of binary, provide an explanation as to why they are so foundational to how computers work, and examine the link between binary numbers and Boolean algebra and its use in databases.

The modern binary number system, which is the basis for binary code, was invented by Gottfried Leibniz in 1689, which he described in his article Explication de l'Arithmétique Binaire (translated as "explanation of binary arithmetic").

Binary numbers are represented in a base-2 system. The only digits used to represent a binary number are "0" and "1." Each digit is called a bit. A binary string of eight bits can represent any of 256 (28) possible values.

A bit string is not the only kind of binary code; other systems that allow only two choices, such as ON/OFF or True/False, can be binary in nature. One such example is Braille, developed by Louis Braille. Braille is widely used by the blind to read and write by touch. This system consists of grids of six dots each, three per column, in which each dot has two states: raised or not raised. Different combinations of these raised or flattened dots represent different letters, numbers, punctuation, and so on. Here are some examples of how alphabets are written in Braille by making use of raised and flattened dots:

Figure 3.3 – Alphabets in Braille

The importance of the binary number system to the development of computers goes way back to 1946, when the first electric general-purpose digital computer – Electronic Numerical Integrator and Computer (ENIAC) – was built at the University of Pennsylvania.

The brain of a computer (the CPU) has many circuits that are made up of a large number of transistors. Transistors are analogous to a "switch" that can be turned to the ON or OFF states based on the signal it receives. The binary digits 0 and 1 reflect the OFF and ON states of a transistor. The user provides the computer with a set of instructions for the computer to do a task. These instructions/commands are translated (by a compiler) into binary code for the computer to understand and execute. All the data, information, music, pictures, and so on are processed and stored in binary form by the computer.

As mentioned before, a 0 or a 1 is called a bit. A group of eight bits is called a byte. Let's try representing multiples of bytes in the decimal and binary systems:

Figure 3.4 – Multiples of bytes and their value in metric and binary systems

The binary interpretation of metric prefixes is used by most operating systems.

Boolean algebra

In this section, we will learn about Boolean algebra in detail, along with its applications, such as logic gates. Boolean operators are very useful in filtering out and viewing data that meets certain criterion; this will be illustrated by using Python to solve an example.

George Boole introduced the idea of Boolean algebra in his book titled The Mathematical Analysis of Logic in 1847. Boolean algebra is a subset of algebra in which values of variables are either "True" (1) or "False" (0). The main operations of Boolean algebra are detailed here.

The AND operator

This operator states that for an output to occur, two or more events must happen simultaneously. However, the order in which the individual events occur is irrelevant. We use & to represent the AND operator. Hence, we can say that A & B = B & A, which means it agrees with commutative law.

Boolean algebra has applications in electronics. Let's try to understand the AND operator by making use of a simple electric circuit comprising a lamp, a battery, and two switches (A and B), as shown in the following figure:

Figure 3.5 – A circuit showing an AND operator

For the lamp to glow, both switches A and B must be in the "ON" (1) position. If either of the switches is ON with the other in the OFF position, then the circuit is incomplete, and the lamp does not glow. The following figure shows the application of Boolean algebra of 0 and 1 to electronic hardware comprising logic gates connected to form a circuit diagram:

Figure 3.6 – AND gates

If A and B are switches, then both must be closed (=1) for the circuit to be closed and the current to flow. If either of the switches is open, then the circuit is open and the current does not flow.

Mathematically, it can be written as A ^ B. If A=1 and B=1, then A ^ B =1, otherwise A ^ B = 0. This can be represented by the following figure:

Figure 3.7 – The AND operator

Let's learn about the OR operator in the next section.

The OR operator

This operator states that for an output to occur, either of two conditions needs to be true. Let's try to understand this by making use of electric circuits. In Figure 3.8, we can see that the circuit will be closed, and the lamp will glow if either switch A is ON or switch B is ON, or both are ON:

Figure 3.8 – A circuit showing the OR operator

Mathematically, this can be written as A V B:

If A=1, B=1, then A V B =1.

If A=0, B=0, then A V B =0.

If A=1, B=0, then A V B =1.

If A=0, B=1, then A V B =1.

This can be represented by the following figure:

Figure 3.9 – The OR operator

The AND and OR operators can be summarized by making use of truth tables as shown in Figure 3.10. Here, 0 = False/OFF and 1 = True/ON:

Figure 3.10 – A truth table for the AND and OR operators

Now that we know how the OR operator works, we will learn about the NOT operator in the next section.

The NOT operator

This operator is used to reverse the truth value of an entire expression, from False to True or from True to False, depending on the situation.

Let's say that a university wants to send a warning email to students whose GPA is less than 2.0. This statement can be reframed in another way – send a warning email to students whose GPA is not greater than 2.0.

This operator can be represented by ¬A:

Figure 3.11 – The NOT operator

The NOT operator is represented in a circuit diagram/logic gate as shown in the following figure:

Figure 3.12 – The NOT operator

The NOT operator can be summarized by making use of a truth table as shown in Figure 3.12. Here, 0 = False/OFF and 1 = True/ON:

Figure 3.13 – A truth table for the NOT operator

Let's see how we can use all this theory about Boolean operators in an example.

Example – Netflix users

Boolean operators can be used to select and view data that satisfies a certain criterion. Let's use the following table to show how our operators can be used in Python. Figure 3.13 shows the customer addresses for 10 customers of Netflix:

Figure 3.14 – Netflix customer dataset

For this example, we will be using a Python library called pandas. It is a fast, flexible, and easy-to-use open source data analysis and manipulation tool that is built on the top of the Python programming language.

Important note

Installing Python packages, such as pandas in this instance, is an important skill that everyone needs. Here's a link with detailed instructions regarding how to install different packages in Python: https://packaging.python.org/tutorials/installing-packages/.

In addition, we will need to import our data to Python in order to use the code in this example. The data is stored in a Comma-Separated Value (CSV) file provided on GitHub called CustomerList.csv, which is available in the GitHub repository for this book. Be sure to download it and store it in the same directory where you store your code.

We will do the following for this example:

• Use the AND operator to view the customers who live in the USA (AND) in the state of Georgia.
• Use the OR operator to view the customers who live either live in the USA or in the state of Ontario.
• Use the NOT operator to view the customers who do not live in the USA.

The Python code is as follows:

# Import packages with the functions we need

import pandas as pd

# Import the file you are trying to work with

customer_df = pd.read_csv("CustomerList.csv")

# Using AND operator

print("Example for AND operator")

print(customer_df.loc[(customer_df['Country'] == 'USA') &

  (customer_df['State'] == 'Georgia')])

# Using OR operator

print("Example for OR operator")

print(customer_df.loc[(customer_df['Country'] == 'USA') |

  (customer_df['State'] == 'Ontario')])

# Using NOT operator

print("Example for NOT operator")

print(customer_df.loc[(customer_df['Country'] != 'USA')])

The output is as follows:

Example for AND operator

   CustomerID Country    State     City Zip Code

0           1     USA  Georgia  Atlanta    30332

1           2     USA  Georgia  Atlanta    30331

Example for OR operator

   CustomerID Country    State       City Zip Code

0           1     USA  Georgia    Atlanta    30332

1           2     USA  Georgia    Atlanta    30331

2           3     USA  Florida  Melbourne    30912

3           4     USA  Florida      Tampa    30123

9          10  Canada  Ontario    Toronto  M4B 1B3

Example for NOT operator

   CustomerID  Country        State        City Zip Code

4           5    India    Karnataka  Bangalore    560001

5           6    India  Maharashtra      Mumbai   578234

6           7    India    Karnataka       Hubli   569823

7           8   India   Maharashtra      Mumbai   578234

8           9  Germany      Bavaria      Munich    80331

9          10   Canada      Ontario     Toronto  M4B 1B3

In the preceding example, we were able to display records that match a certain criterion – the first task was to view the customers that reside in the USA and in the state of Georgia. Records matching both these requirements were then displayed. Similarly, for the second part of the example, we were able to view the records of customers who either live in the USA or in the state of Ontario (in Canada). We used the OR operator to achieve this goal. Lastly, we used the NOT operator to view all the records for customers that do not reside in the USA; all the results except for the ones who reside in the USA were displayed.

In this section, we learned about different kinds of logical operators and how they can be used to search and view results that match a certain criterion. In the next section, we will be discussing another kind of number system, called the hexadecimal number system, and learning about its application.

Hexadecimal numbers and their application

In this section, we will learn about the hexadecimal number system and its application. We use hexadecimal numbers in our day-to-day lives without realizing, such as for the MAC address of your phone or computer.

Hexadecimal numbers are base-16 numbers. They can be represented by using 10 digits (0 to 9) and 6 letters (A = 10, B = 11, C = 12, D = 13, E = 14, F = 15).

Let's look at some conversions between the decimal and hexadecimal number systems:

Figure 3.15 – Counting in hexadecimal

Just like decimal numbers, hexadecimal numbers also have place values:

(100)16 = (1 ∙ 162) + (0 ∙ 161) + (0 ∙ 160) = 256

Computer programmers use hexadecimal numbers to simplify the binary number system. We know that 24 = 16, so we know there is a linear relationship between 2 and 16, which implies that four binary digits would be equivalent to one hexadecimal digit. In other words, since binary numbers can be represented by two digits (0 or 1) and hexadecimal numbers can be represented by 16 digits and letters, and we can write 16 as a power of 2 (24), four binary digits would be equivalent to one hexadecimal digit. While computers use the binary numbering system, humans use the hexadecimal system to make things easier to understand.

Example – Defining locations in computer memory

In the previous section, we learned that 1 byte = 8 bits. Hexadecimal numbers can characterize every byte as two hexadecimal digits as compared to eight digits when the binary number system is used.

Let's work through an example to better understand how memory locations are defined on a computer, how different variables are stored in different memory locations, and how the values assigned to variables (and, hence, the memory locations) can be changed. We will do the following for this example:

• We will define a peanut_butter variable and assign the value 6 to it. We will then print the memory location of where this variable is stored.
• We will define another variable, sandwich, and assign it the same value as peanut_butter. When we print the memory location of this variable, we will see that it is the same as for peanut_butter. This is because we assigned the same value (6) to both our variables, and so they were stored in the same memory location.
• We will move on to assign 7 to the sandwich variable and then set both the peanut_butter and sandwich variables to each other. We can check that they both return the same memory location.
• We'll then set sandwich to 10; this changes the value (and memory location) of the sandwich variable only, and nothing changes for the peanut_butter variable.

Let's see how to implement this in Python:

#Variable 1: peanut_butter

peanut_butter = 6

print("The memory location of variable peanut_butter is:

  ",id(peanut_butter))

#Variable 2: sandwich

sandwich = 6

print("The memory location of variable sandwich is:

  ",id(sandwich))

print(" We can see that the memory location of both the

  variables is the same because they were assigned the same

    value")

#Setting value of sandwich variable to a new number

sandwich = 7

#Setting both the variables equal to each other:

peanut_butter = sandwich

print("After setting the values of both variables equal to each

  other, we have: ")

print("The value of variable sandwich is now set to:

  ",sandwich)

print("The value of variable peanut_butter is now set to:

  ",peanut_butter)

print("The value of  sandwich variable was changed to 10, let's

  see whether it affects the value of peanut_butter")

#Setting value of sandwich variable to a new number

sandwich = 10

print("The value of variable peanut_butter: " ,peanut_butter)

print("The value of peanut_butter did NOT change even though we

  changed the value of sandwich")

print("The memory location of variable peanut_butter is:

  ",id(peanut_butter))

The output of the code is as follows:

The memory location of variable peanut_butter is:  2077386960

The memory location of variable sandwich is:  2077386960

We can see that the memory location of both the variables is

  the same because they were assigned the same value

After setting the values of both variables equal to each other, we have:

The value of variable sandwich is now set to:  7

The value of variable peanut_butter is now set to:  7

The value of variable was changed to 10, let's see whether it

affects the value of peanut_butter

The value of variable peanut_butter:  7

The value of peanut_butter did NOT change even though we

changed the value of sandwich

The memory location of variable peanut_butter is:  2077386976

Now that we know how hexadecimal numbers are used to define memory locations, let's move on to see some more examples of how they are useful.

Example – Displaying error messages

Hexadecimal numbers represent the memory location of errors, making it easier for the user to find and fix them. A binary representation, which would be the most natural representation due to the way a CPU works, would include four times as many digits, which would be difficult for a human to read and interpret.

Example – Media Access Control (MAC) addresses

MAC addresses are unique identifiers assigned to the Network Interface Card (NIC) of any computer. An NIC is required in order to connect to other computers in a network. It is useful for uniquely identifying a computer among other computers. The format of a MAC address is either AA:AA:AA:BB:BB:BB or AAAA-AABB-BBBB:

Figure 3.16 – A MAC address

We can easily write some Python code to find the MAC address of the device on which it is running by writing the following code in the terminal:

import uuid

# address using uuid and getnode() function

# making use of hexadecimal number system

print (hex(uuid.getnode()))

It has the following output:

0xf40669da5f06

Now that we know how to find the MAC address of our computers, let's move on to see how the hexadecimal number system can be used to define colors.

Example – Defining colors on the web

The primary colors – red (R), green (G), and blue (B) – are represented by two hexadecimal digits each. This can be written as #RRGGBB. Primary colors cannot be created by mixing other colors.

The values of red, green, and blue can be set between 0 and 255 to generate other colors. Figure 3.17 lists all the commonly used colors:

Figure 3.17 – For each RGB value, we have written the value in decimal and the two-digit hex number in parentheses in columns 2-4

The advantages of hexadecimal number system:

• It's a concise number system, so we can store more information by using less memory space.
• It is more human-friendly because it allows the grouping of binary numbers.

In this section, we learned about hexadecimal numbers and some of their applications, which included defining locations in computer memory, MAC addresses for devices, displaying error messages, and defining colors on a web page.

Summary

In this chapter, we learned about numbers in different bases (decimal, binary, hexadecimal) and how we can convert between bases. Binary numbers are a base-2 number system, whereas decimal numbers are base-10 and hexadecimal numbers are base-16, respectively. We also learned about one very crucial application of the binary number system – Boolean algebra and Boolean operators.

In the next chapter, we will be learning about combinatorics, which includes the study of permutations and combinations that will enable you to calculate the amount of memory required to store certain kinds of data. In addition, we will learn about hashing and the efficacy of brute force algorithms.