Start Concurrent: A Gentle Introduction to Concurrent Programming

The processor, or central processing unit (CPU), is the “brain” of a computer. It fetches instructions, decodes them, and executes them. It may send data to or from memory or I/O devices. The CPU on virtually all modern computers is a microprocessor, meaning that all the computation is done by an integrated circuit fabricated out of silicon. What are the important features of CPUs? How do we measure their speed and power?

Memory is where all the programs and data on a computer are stored. The memory in a computer is usually not a single piece of hardware. Instead, the storage requirements of a computer are met by many different technologies.

At the top of the pyramid of memory is primary storage, memory that the CPU can access and control directly. On desktop and laptop computers, primary storage usually takes the form of random access memory (RAM). It is called random access memory because it takes the same amount of time to access any part of RAM. Traditional RAM is volatile, meaning that its contents are lost when it’s unpowered. All programs and data must be loaded into RAM to be used by the CPU.

After primary storage comes secondary storage. The realm of secondary storage is dominated by hard drives that store data on spinning magnetic platters though flash technology is beginning to replace them. Optical drives (such as CD, DVD, and Blu-ray) and the now virtually obsolete floppy drives also fall into the category of secondary storage. Secondary storage is slower than primary storage, but it is non-volatile. Some forms of secondary storage such as CD-ROM and DVD-ROM are read only, but most are capable of reading and writing.

Before we can compare these kinds of storage effectively, we need to have a system for measuring how much they store. In modern digital computers, all data is stored as a sequence of 0s and 1s. In memory, the space that can hold either a single 0 or a single 1 is called a bit, which is short for “binary digit.”

A bit is a tiny amount of information. For organizational purposes, we call a sequence of eight bits a byte. The word size of a CPU is two or more bytes, but memory capacity is usually listed in bytes not words.

Both primary and secondary storage capacities have become so large that it is inconvenient to describe them in bytes. Computer scientists have borrowed prefixes from physical scientists to create suitable units.

Common units for measuring memory are bytes, kilobytes, megabytes, gigabytes, and terabytes. Each unit is 1,024 times the size of the previous unit. You may have noticed that 2¹⁰ (1,024) is almost the same as 10³ (1,000). Sometimes it’s not clear which value is meant. Disk drive manufacturers always use powers of 10 when they quote the size of their disks. Thus, a 1 TB hard disk might hold 10¹² (1,000,000,000,000) bytes, not 2⁴⁰ (1,099,511,627,776) bytes. Standards organizations have advocated that the terms kibibyte (KiB), mebibyte (MiB), gibibyte (GiB), and tebibyte (TiB) be used to refer to the units based on powers of 2 while the traditional names be used to refer only to the units based on powers of 10, but the new terms have not yet become popular.

We called memory a pyramid earlier in this section. At the top there’s a small but very fast amount of memory. As we work down the pyramid, the storage capacity grows, but the speed slows down. Of course, the pyramid for every computer is different. Below is a table that shows many kinds of memory moving from the fastest and smallest to the slowest and largest. Effective speed is hard to measure (and is changing as technology progresses), but note that each layer in the pyramid tends to be 10-100 times slower than the previous layer.

I/O devices have much more variety than CPUs or memory. Some I/O devices, such as USB ports, are permanently connected by a printed circuit board to the CPU. Other devices called peripherals are connected to a computer as needed. Their types and features are many and varied, and this book does not go deeply into how to interact with I/O devices.

Common input devices include mice, keyboards, touch pads, microphones, game pads, and drawing tablets. Common output devices include monitors, speakers, and printers. Some devices perform both input and output, such as network cards.

Remember that our view of computer hardware as CPU, memory, and I/O devices is only a model. A PCI Express socket can be considered an I/O device, but the graphics card that fits into the socket can be considered one as well. And the monitor that connects to the graphics card is yet another one. Although the graphics card is an I/O device, it has its own processor and memory, too. It’s pointless to get bogged down in details unless they are relevant to the problem you’re trying to solve. One of the most important skills in computer science is finding the right level of detail and abstraction to view a given problem.

A number system is a way to represent numbers. It’s easy to confuse the numeral that represents the number with the number itself. You might think of the number ten as “10”, a numeral made of two symbols, but the number itself is the concept of ten-ness. You could express that quantity by holding up all your fingers, with the symbol “X”, or by knocking ten times.

Representing ten with “10” is an example of a positional number system, namely base 10. In a positional number system, the position of the digits determines the magnitude they represent. For example, the numeral 3,432 contains the digit 3 twice. The first time, it represents three groups of one thousand. The second time, it represents three groups of ten. In contrast, the Roman numeral system is an example of a number system that is not positional.

The numeral 3,432 and possibly every other normally written number you’ve seen is expressed in base 10 or the decimal system. It’s called base 10 because, as you move from the rightmost digit leftward, the value of each position goes up by a factor of 10. Also, in base 10, ten is the smallest positive integer that requires two digits for representation. Each smaller number has its own digit: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Representing ten requires two existing digits to be combined. Every base has the property that the number it’s named after takes two digits to write, namely “1” and “0.” (An exception is base 1, which does not behave like the other bases and is not a normal positional number system.)

We can extend these ideas to any base, checking our logic against the familiar base 10. Suppose that a numeral consists of n symbols s_n-1, s_n-2, …, s₁, s₀. Furthermore, suppose that this numeral belongs to the base b number system. We can expand the value of this numeral as:

The leftmost symbol in the numeral is the highest order digit and the rightmost symbol is the lowest order digit. For example, in the decimal numeral 492, 4 is the highest order digit and 2 the lowest order digit.

Fractions can be expanded in a similar manner. For example, a fraction with n symbols s₁, s₂, …, s_n-1, s_n in a number system with base b can be expanded to:

As computer scientists, we have a special interest in base 2 because that’s the base used to express numbers inside of computers. Base 2 is also called binary. The only symbols allowed to represent numbers in binary are “0” and “1”, the binary digits or bits.

In the binary numeral 10011, the leftmost 1 is the highest order bit and the rightmost 0 is the lowest order bit. By the rules of positional number systems, the highest order bit represents 1 ⋅ 2⁴ = 16.

Another useful number system is base 16, also known as hexadecimal. Hexadecimal is surprising because it requires more than the familiar 10 digits. Numerals in this system are written with 16 hexadecimal digits that include the ten digits 0 through 9 and the six letters A, B, C, D, E, and F. The six letters, starting from A, correspond to the values 10, 11, 12, 13, 14, and 15.

Hexadecimal is used as a compact representation of binary. Although binary numbers can get very long, four binary digits can be represented with only a single hexadecimal digit.

The base 8 number system is also called octal. Like hexadecimal, octal is used as a shorthand for binary. A numeral in octal uses the octal digits 0, 1, 2, 3, 4, 5, 6, and 7. Otherwise the same rules apply. For example, the octal numeral 377 can be expanded to:

You may have noticed that it is not always clear which base a numeral is written in. The digit sequence 337 is a legal numeral in octal, decimal, and hexadecimal, but it represents different numbers in each system. Mathematicians use a subscript to denote the base in which a numeral is written.

Thus, 337₈ = 255₁₀, 377₁₀ = 377₁₀, and 377₁₆ = 887₁₀. Base numbers are always written in base 10. A number without a subscript is assumed to be in base 10. In Java, there’s no way to mark subscripts, so prefixes are used. A prefix of 0 is used for octal, no prefix is used for decimal, and a prefix of 0x is used for hexadecimal. A numeral cannot be marked as binary in Java. The corresponding numerals in Java code would thus be written 0377, 377, and 0x377. Be careful not to pad numbers with zeroes in Java since they might be interpreted as base 8! Remember that the value 056 is not the same as the value 56 in Java.

The following table lists a few characteristics of the four number systems we have discussed with representations of the numbers 7 and 29.

It’s useful to know how to convert a number represented in one base to the equivalent representation in another base. Our examples have shown how to convert a numeral in any base to decimal by expanding the numeral in the sum-of-product form and then adding the different terms together. But how do you convert a decimal numeral to another base?

There are at least two different ways to convert a decimal numeral to binary. One way is to write the decimal number as a sum of powers of two as in the following conversion of the number 23.

First, find the largest power of two that’s less than or equal to the number. In this case, 16 fits the bill because 32 is too large. Subtract that value from the number, leaving 7 in this case. Then repeat the process. The last step is to collect the coefficients of the powers of two into a sequence to get the binary equivalent. We used 16, 4, 2, and 1 but skipped 8. If we write a 1 for every place we used and a 0 for every place we skipped, we get 23 = 10111₂. While this is a straightforward procedure for decimal to binary conversion, it can be cumbersome for larger numbers.

An alternate way to convert a decimal numeral to an equivalent binary numeral is to divide the given number by 2 until the quotient is 0 (keeping only the integer part of the quotient). At each step, record the remainder found when dividing by 2. Collect these remainders (which will always be either 0 or 1) to form the binary equivalent. The least significant bit is the remainder obtained after the first division, and the most significant bit is the remainder obtained after the last division. In other words, this approach finds the digits of the binary number in backward order.

A decimal number can be converted to its hexadecimal equivalent using either of the two procedures described above. Instead of writing a decimal number as a sum of powers of 2, one writes it as a sum of powers of 16. Similarly, when using the division method, instead of dividing by 2, one divides by 16. Octal conversion is similar.

We use hexadecimal because it’s straightforward to convert from it to binary or back. The following table lists binary equivalents for the 16 hexadecimal digits.

With the help of the table above, let’s convert 3FA₁₆ to binary. By simple substitution, 3FA₁₆ = 0011 1111 1010₂. Note that we’ve grouped the binary digits into clusters of 4 bits each. Of course, the leftmost zeroes in the binary equivalent are useless as they do not contribute to the value of the number.

In mathematics, binary numerals can represent arbitrarily big numbers. Inside of a computer, the size of a number is constrained by the number of bits used to represent it. For general purpose computation, 32- and 64-bit integers are commonly used. The largest integer that Java represents with 32 bits is 2,147,483,647, which is good enough for most tasks. For larger numbers, Java can represent up to 9,223,372,036,854,775,807 with 64 bits. Java also provides representations for integers using 8 and 16 bits.

These representations are easy to determine for positive numbers: Find the binary equivalent of the number and then pad the left side with zeroes to fill the remaining space. For example, 19 = 10011₂. If stored using 8 bits, 19 would be represented as 0001 0011. If stored using 16 bits, 19 would be represented as 0000 0000 0001 0011. (We separate groups of 4 bits for easier reading.)

Recall that computers deal with numbers in their binary representation, meaning that all arithmetic is done on binary numbers. Sometimes it’s useful to understand how this process works and compare it to decimal arithmetic. The table below lists rules for binary addition.

As indicated above, the addition of two 1s leads to a 0 with a carry of 1 into the next position to the left. Addition for numbers composed of more than one bit use the same rules as any addition, carrying values that are too large into the next position. In decimal addition, values over 9 must to be carried. In binary addition, values over 1 must be carried. The next example shows a sample binary addition. To simplify its presentation, we assume that the integers are represented with only 8 bits.

Subtraction in binary is also similar to subtraction in decimal. The rules are given in the following table.

When subtracting a 1 from a 0, a 1 is borrowed from the next left position. The next example illustrates binary subtraction.

Negative integers are also represented in computer memory as binary numbers, using a system called two’s complement. When looking at the binary representation of a signed integer in a computer, the leftmost (most significant) bit will be 1 if the number’s negative and 0 if it’s positive. Unfortunately, there’s more to finding the representation of a negative number than flipping this bit.

Suppose that we need to find the binary equivalent of the decimal number -12 using 8 bits in two’s complement form. The first step is to convert 12 to its 8-bit binary equivalent. Doing so we get 12 = 0000 1100. Note that the leftmost bit of the representation is a 0, indicating that the number is positive. Next, we take the two’s complement of the 8-bit representation in two steps. In the first step, we flip every bit, i.e., change every 0 to 1 and every 1 to 0. This gives us the one’s complement of the number, 1111 0011. In the second step, we add 1 to the one’s complement to get the two’s complement. The result is 1111 0011 + 1 = 1111 0100.

Thus, the 8-bit, two’s complement binary equivalent of -12 is 1111 0100. Note that the leftmost bit is a 1, indicating that this is a negative number.

Why do computers use two’s complement? First of all, they need a system that can represent both positive and negative numbers. They could have used the leftmost bit as a sign bit and represented the rest of the number as a positive binary number. Doing so would require a check on the bit and some conversion for negative numbers every time a computer wanted to perform an addition or subtraction.

Because of the way it’s designed, positive and negative integers stored in two’s complement can be added or subtracted without any special conversions. The leftmost bit is added or subtracted just like any other bit, and values that carry past the leftmost bit are ignored. Two’s complement has an advantage over one’s complement in that there is only one representation for zero. The next example shows two’s complement in action.

When performing arithmetic on numbers, an overflow is said to occur when the result of the operation is larger than the largest value that can be stored in that representation. An underflow is said to occur when the result of the operation is smaller than the smallest possible value.

Both overflows and underflows lead to wrapped-around values. For example, adding two positive numbers together can result in a negative number or adding two negative numbers together can result in a positive number.

The smallest (most negative) number that can be represented in 8-bit two’s complement is -128. A result smaller than this will result in underflow. For example, -115 - 31 = 110. Try out the conversions needed to test this result.

Although we most commonly manipulate numbers using traditional mathematical operations such as addition, subtraction, multiplication, and division, there are also operations that work directly on the binary representations of the numbers. Some of these operators have clear relationships to mathematical operations, and some don’t.

Bitwise AND, bitwise OR, and bitwise XOR take two integer representations and combine them to make a new representation. In bitwise AND, each bit in the result will be a 1 if both of the original integer representations in that position are 1 and 0 otherwise. In bitwise OR, each bit in the result will be a 1 if either of the original integer representations in that position are 1 and 0 otherwise. In bitwise XOR, each bit in the result will be a 1 if the two bits of the original integer representations in that position are different and 0 otherwise.

Bitwise complement is a unary operator like the negation operator (-). Instead of merely changing the sign of a value (which it will also do), its result changes every 1 in the original representation to 0 and every 0 to 1.

The signed left shift, signed right shift, and unsigned right shift operators all create a new binary representation by shifting the bits in the original representation a certain number of places to the left or the right. The signed left shift moves the bits to the left, padding with 0s. If you do a signed left shift by n positions, it’s equivalent to multiplying the number by 2ⁿ (until overflow occurs). The signed right shift moves the bits to the right, padding with whatever the sign bit is. If you do a signed right shift by n positions, it’s equivalent to dividing the number by 2ⁿ (with integer division). The unsigned right shift moves the bits to the right, including the sign bit, filling the left side with 0s. An unsigned right shift will always make a value positive but is otherwise similar to a signed right shift. A few examples follow.

We’ve seen how to represent positive and negative integers in computer memory, but this section shows how rational numbers, such as 12.33, -149.89, and 3.14159, can be converted into binary and represented.

Scientific notation is closely related to the way a computer represents a rational number in memory. Scientific notation is a tool for representing very large or very small numbers without writing a lot of zeroes. A decimal number in scientific notation is written a × 10^b where a is called the mantissa and b is called the exponent.

For example, the number 3.14159 can be written in scientific notation as 0.314159 × 10¹. In this case, 0.314159 is the mantissa, and 1 is the exponent. Here a few more examples of writing numbers in scientific notation.

There are many ways of writing any given number in scientific notation. A more standardized way of writing real numbers is normalized scientific notation. In this notation, the mantissa is always written as a number whose absolute value is less than 10 but greater than or equal to 1. Following are a few examples of decimal numbers in normalized scientific notation.

A shorthand for scientific notation is E notation, which is written with the mantissa followed by the letter ‘E’ followed by the exponent. For example, 39.2 in E notation can be written 3.92E1 or 0.392E2. The letter ‘E’ should be read “multiplied by 10 to the power.” It’s legal to use E notation to represent numbers in scientific notation in Java.

A rational number can be broken into an integer part and a fractional part. In the number 3.14, 3 is the integer part, and .14 is the fractional part. We’ve already seen how to convert the integer part to binary. Now, we’ll see how to convert the fractional part into binary. We can then combine the binary equivalents of the integer and fractional parts to find the binary equivalent of a decimal real number.

A decimal fraction f is converted to its binary equivalent by successively multiplying it by 2. At the end of each multiplication step, either a 0 or a 1 is obtained as an integer part and is recorded separately. The remaining fraction is again multiplied by 2 and the resulting integer part recorded. This process continues until the fraction reduces to zero or enough binary digits for the desired precision have been found. The binary equivalent of f then consists of the bits in the order they have been recorded, as shown in the next example.

In some cases the process described above will never have a remainder of 0. Then, we can only find an approximate representation of the given fraction as demonstrated in the next example.

Now that we understand how integers as well as fractions can be converted from one number base to another, we can convert any rational number from one base to another. The next example demonstrates one such conversion.

Floating-point representation is a system used to represent rational numbers in computer memory. In this notation a number is represented as a × b^e, where a gives the significant digits (mantissa) of the number and e is the exponent. The system is very similar to scientific notation, but computers usually use base b = 2 instead of 10.

For example, we could write the binary number 1010.1₂ in floating-point representation as 10.101₂ × 2² or as 101.01₂ × 2¹. In any case, this number is equivalent to 10.5 in decimal.

In standardized floating-point representation, a is written so that only the most significant non-zero digit is to the left of the decimal point. Most computers use the IEEE 754 floating-point representation to represent rational numbers. In this notation, the memory to store the number is divided into three segments: one bit used to mark the sign of the number, m bits to represent the mantissa (also known as the significand), and e bits to represent the exponent.

In IEEE floating-point representation, numbers are commonly represented using 32 bits (known as single precision) or using 64 bits (known as double precision). In single precision, m = 23 and e = 8. In double precision, m = 52 and e = 11. To represent positive and negative exponents, the exponent has a bias added to it so that the result is never negative. This bias is 127 for single precision and 1,023 for double precision. The packing of the sign bit, the exponent, and the mantissa is shown in Figure 1.4 (a) and (b).

Fixing the number of bits used for representing a real number limits the numbers that can be represented in computer memory using the floating-point notation. The largest rational number that can be represented in single precision has an exponent of 127 (254 after bias) with a mantissa consisting of all 1s:
0 1111 1110 1111 1111 1111 1111 1111 111
This number is approximately 3.402 × 10³⁸. To represent the smallest (closest to zero) non-zero number, we need to examine one more complication in the IEEE format. An exponent of 0 implies that the number is unnormalized. In this case, we no longer assume that there is a 1 bit to the left of the mantissa. Thus, the smallest non-zero single precision number has its exponent set to 0 and its mantissa set to all zeros with a 1 in its 23^rd bit:
0 0000 0000 0000 0000 0000 0000 0000 001
Unnormalized single precision values are considered to have an exponent of -126. Thus, the value of this number is 2^-23 × 2^-126 = 2^-149 ≈ 1.4 × 10^-45. Now that we know the rules for storing both integers and floating-point numbers, we can list the largest and smallest values possible in 32- and 64-bit representations in Java in the following table. Note that largest means the largest positive number for both integers and floating-point values, but smallest means the most negative number for integers and the smallest positive non-zero value for floating-point values.

Using the same number of bits, floating-point representation can store much larger numbers than integer representation. However, floating-point numbers are not always exact, resulting in approximate results when performing arithmetic. Always use integer formats when fractional parts aren’t needed.

Several binary representations in the floating-point representation correspond to special numbers. These numbers are reserved and do not have the values that would be expected from normal multiplication of the mantissa by the power of 2 given by the exponent.

As we have seen, many rational numbers can only be approximately represented in computer memory. Thus, arithmetic done on the approximate values yields approximate answers. For example, 1.3 cannot be represented exactly using a 64-bit value. In this case, the product 1.3 * 3.0 will be 3.9000000000000004 instead of 3.9. This error will propagate as additional operations are performed on previous results. The next example illustrates this propagation of errors when a sequence of floating-point operations are performed.

While the above example may seem unrealistic, it does expose the inherent dangers of floating-point calculations. Although the error is less when using double precision representations, it still exists.

Multicore systems have impressive performance. The first multicore processors had two cores, but current designs have four, six, eight, or higher. A processor with eight cores can execute eight different programs at the same time. Or, when faced with a computationally intense problem like matrix math, code breaking, or scientific simulation, a processor with eight cores could solve the problem eight times as fast. A desktop processor with 100 cores that can solve a problem 100 times faster is not out of reach.

In fact, modern graphics cards are already blazing this trail. Consider the 1080p standard for high definition video, which has a resolution of 1,920 × 1,080 pixels. Each pixel (short for picture element) is a dot on the screen. A screen whose resolution is 1080p has 2,073,600 dots. To maintain the illusion of smooth movement, these dots should be updated around 30 times per second. Computing the color for more than 2 million dots based on 3D geometry, lighting, and physics effects 30 times a second is no easy feat. Some of the cards used to render computer games have hundreds or thousands of cores. These cores are not general purpose or completely independent. Instead, they’re specialized to do certain kinds of matrix transformations and floating-point computations.

Although chip-makers have spent a lot of money marketing multicore technology, they haven’t spent much money explaining that one of the driving forces behind the “multicore revolution” is a simple failure to make processors faster in other ways. In 1965, Gordon Moore, one of the founders of Intel, remarked that the density of silicon microprocessors had been doubling every year (though he later revised this to every two years), meaning that twice as many transistors (computational building blocks) could fit in the same physical space. This trend, often called Moore’s Law, has held up reasonably well. For years, clever designs relying on shorter communication times, pipelining, and other schemes succeeded in doubling the effective performance of processors every two years.

At some point, the tricks became less effective and exponential gains in processor clock rate could no longer be sustained. As clock frequency increases, the signal becomes more chaotic, and it becomes more difficult to tell the difference between the voltages that represent 0s and 1s. Another problem is heat. The energy that a processor uses is related to the square of the clock rate. This relationship means that increasing the clock rate of a processor by a factor of 4 will increase its energy consumption (and heat generation) by a factor of 16.

The legacy of Moore’s Law lives on. We’re still able to fit more and more transistors into tinier and tinier spaces. After decades of increasing clock rate, chip-makers began using the additional silicon density to make processors with more than one core instead. Since 2005 or so, increases in clock rate have stagnated.

Does a processor with eight cores solve problems eight times as fast as its single core equivalent? Unfortunately, the answer is, “Almost never.” Most problems are not easy to break into eight independent pieces.

For example, if you want to build eight houses and you have eight construction teams, then you probably can get pretty close to completing all eight houses in the time it would have taken for one team to build a single house. But what if you have eight teams and only one house to build? You might be able to finish the house a little early, but some steps necessarily come after others: The concrete foundation must be poured and solid before framing can begin. Framing must be finished before the roof can be put on. And so on.

Like building a house, most problems you can solve on a computer are difficult to break into concurrent tasks. A few problems are like painting a house and can be completed much faster with lots of concurrent workers. Other tasks simply cannot be done faster with more than one team on the job. Worse, some jobs can actually interfere with each other. If a team is trying to frame the walls while another team is trying to put the roof onto unfinished walls, neither will succeed, the house might be ruined, and people could get hurt.

On a desktop computer, individual cores generally have their own level 1 cache but share level 2 cache and RAM. If the programmer isn’t careful, he or she can give instructions to the cores that will make them fight with each other, overwriting memory that other cores are using and crashing the program or giving an incorrect answer. Imagine if different parts of your brain were completely independent and fought with one another. The words that came out of your mouth might be gibberish.

To recap, the first problem with concurrent programming is finding ways to break down problems so that they can be solved faster with multiple cores. The second problem is making sure that the different cores cooperate so that the answer is correct and makes sense. These are not easy problems, and many researchers are still working on finding better ways to do both.

Some educators believe that beginners will be confused by concurrency and should wait until later courses to confront these problems. We disagree: Forewarned is forearmed. Concurrency is an integral part of modern computation, and the earlier you get introduced to it, the more familiar it’ll be.

Methods allow us to perform actions in Java. They are blocks of code packaged up with a name so that we can run the same piece of code repeatedly but with different inputs. We discuss them in much greater depth in Chapter 8.

A common method for output is System.out.print(). The input (usually called arguments) to a method are given between its parentheses. Thus, if we want to print 42 to the terminal, we type:

Note that the use of the method has a semicolon (;) after it. An executable line of code in Java generally ends with a semicolon to separate it from the next instruction. We can add this code to our Example class, yielding:

If we want to print out text, we give it as the argument to System.out.print(), surrounded by double quotes ("). It’s necessary to surround text with quotes so that Java knows it’s text and not the name of a class, method, or variable. Text surrounded by double quotes is called a string. The following program prints Forty two onto the terminal.

Printing out one thing is great, but programs are usually composed of many instructions. Consider the following program:

As you can see, each executable line ends with a semicolon, and they are executed in sequence. This code prints 2, 4, 6, and 8 onto the screen. However, we did not tell the program to move the cursor to a new line at any point so the output on the screen is 2468, which looks like a single number. If we want them to be on separate lines, we can achieve this with the System.out.println() method, which moves to a new line after it finishes output.

This change makes the output into the following:

In Java, it’s possible to insert math almost anywhere. Consider the following program, which uses the + operator.

This code prints out 42 to the terminal just like our earlier example, because it does the addition before giving the result to System.out.print() for output.

We want to be able to read input from the user as well. For command line input, we need to create a Scanner object. This object is used to read data from the keyboard. The following program asks the user for an integer, reads in an integer from the keyboard, and then prints out the value multiplied by 2.

This program introduces several new elements. First, note that it begins with
import java.util.Scanner;. This line of code tells the compiler to use the Scanner class that is in the java.util package. A package is a way of organizing a group of related classes. Someone else wrote the Scanner class and all the other classes in the java.util package, but by importing the package, we’re able to use their code in our program.

Then, skip down to the first line in the main() method. The code Scanner in; declares a variable called in with type Scanner. A variable can hold a value. The variable has a specific type, meaning the kind of data that the value can be. In this case the type is Scanner, meaning that the variable in holds a Scanner object. Declaring a variable creates a box that can hold things of the specified type. To declare a variable, first put the type you want it to have, then put its identifier or name, and then put a semicolon. We chose to call the variable in, but we could have called it input or even marmalade if we wanted. It’s always good practice to name your variable so that it’s clear what it contains.

The next line assigns a value to in. The assignment operator (=) looks like an equal sign from math, but think of it as an arrow that points left. Whatever’s on the right side of the assignment operator will be stored into the variable on the left. The variable in was an initially empty box that could hold a Scanner object. The code new Scanner(System.in) creates a brand new Scanner object based on System.in, which means that the input will be from the keyboard. The assignment stored this object into the variable in. The fact that System.in was used has nothing to do with the fact that our variable was named in. Again, don’t expect to understand all the details at first. Any time you need to read data from the keyboard, you’ll need these two lines of code, which you should be able to copy verbatim. It’s possible to both declare a variable and assign its value in one line. Instead of the two line version, most programmers would type:

Similarly, the line int value; declares a variable for holding integer types. The next line uses the object in to read an integer from the user by calling the nextInt() method. If we wanted to read a floating-point value, we would have called the nextDouble() method. If we wanted to read some text, we would have called the next() method. Unfortunately, these differences means that we have to know what type of data the user is going to enter. If the user enters an unexpected type, our program could have an error. As before, we could combine the declaration and the assignment into a single line:

The final two lines give output for our program. The former prints That number doubled is: to the terminal. The latter prints out a value that is twice whatever the user entered. The next two examples illustrate how Scanner can be used to read input while solving problems. The first example shows how these elements can be applied to subproblem 1 of the bouncing ball problem, and the second example introduces and solves a new problem.

To make our code useful, we can perform operations on values and variables. For example, we used the expression 35 + 7 as an argument to the System.out.print() method to print 42 to the screen. We can use the add (+), subtract (-), multiply (*), and divide(/) operators on numbers to solve arithmetic problems. These operators work the way you’d expect them to (except that division has a few surprises). We’ll go into these operators and others more deeply in Chapter 3. Here are examples of these four operators used with integer and floating-point numbers.

These basic operations can mix values and variables together. As we’ll discuss later, they can be arbitrarily complicated with order of operations determining the final answer. Nevertheless, we also need ways to accomplish other mathematical operations such as raising a number to a power or finding its square root. The Math class has methods that perform these and other functions. To raise a number to a power, we call Math.pow() with two arguments: first the base and then the exponent. To find a square root, we pass a number to the Math.sqrt() method.

Just as we can add numbers together, we can also “add” pieces of text together. In Java, text has the type String. If you use the + operator between two values or variables of type String, the result is a new String that is the concatenation of the two previous String values, meaning that the result is the two pieces of text pasted together, one after the other. Concatenation doesn’t change the String values you’re concatenating.

The results may be illegal or at least unexpected if you mix types (String, int, double) together when doing mathematical operations. However, feel free to concatenate String values with any other type using the + operator. When you do so, the other type is automatically converted into a String. This behavior is useful since any String is easy to output. Here are a few examples of String concatenation.

Java programs are filled with variables, and each variable should be named to reflect its contents. Variable names are essentially unlimited in length (although the JVM you use may limit this length to thousands of characters). A tremendously long variable name can be hard to read, but abbreviations can be worse. You want the meaning of your code to be obvious to others and to yourself when you come back days or weeks later.

Imagine you’re writing a program that sells fruit. Consider the following names for a variable that keeps track of the number of apples.

Mathematics is filled with one letter variables, partly because there’s a history of writing mathematics on chalkboards and paper. Clarity is more important than brevity with variables in computer programs. Some variables need more than one word to be descriptive. In that case, programmers of Java are encouraged to follow camel case. In camel case, multi-word variables and methods start with a lowercase letter and then use an uppercase letter to mark the beginning of each new word. It’s called camel case because the uppercase letters are reminiscent of the humps of a camel. Examples include lastValue, symbolTable, and makeHamSandwich().

By convention, class names should always begin with a capital letter, but they also use camel case, marking the beginning of each new word with an uppercase letter. Examples include LinkedList, JazzPiano, and GlobalNuclearWarfare.

Another convention is that constants, variables whose values never change, have names in all uppercase, separated by underscores. Examples include PI, TRIANGLE_SIDES, and UNIVERSAL_GRAVITATIONAL_CONSTANT.

Spaces are not allowed in variable, method, or class names. Recall that a name in Java is called an identifier. The rules for identifiers specify that they must start with an uppercase or lowercase letter (or an underscore) and that the remaining characters must be letters, underscores, or numerical digits. Thus, Tupac and the absurd _5 are legal identifiers, but Motley Crue and 2Pac are not.

In Java, letters can mean more than just the Latin letters A through Z. Java has support for many of the world’s languages, allowing identifiers to contain characters from Chinese, Thai, Devanagari, Cyrillic, and other scripts. For example, m\u00F6tleyCr\u00FCe is a legal variable name because \u00F6 is way of encoding ö and \u00FC is a way of encoding ü. In some systems, this variable name might be rendered mötleyCrüe, but the compiler could complain if you type those characters in directly. In short, Java supports a huge range of characters, but making that support work for you is sometimes more challenging. Section 3.3.2.10 discusses character encoding further.

Remember that keywords also cannot be used as identifiers. For example, public, static, and class are all keywords in Java and can never be the names of classes, variables, or methods.

Although you are not allowed to have spaces in a Java identifier, you can usually use white space (spaces, tabs, and new lines) wherever you want. Java ignores extra space. Consider the following line of code.

It’s equivalent to the next one.

We chose to type our earlier example of a program performing output as follows.

However, we could have been more chaotic with our use of whitespace.

Or we could have used almost no whitespace at all.

These three programs are identical in the eyes of the Java compiler, but the first one is easier for a human to read. You should use whitespace to increase readability. Don’t add too much whitespace with lots of blank lines between sections of code. On the other hand, don’t use too little and cramp the code together. Whenever code is nested inside of a set of braces, indent the contents so that it’s easy to see the hierarchical relationship.

The style we present in this book puts the left brace ({) on the line starting a block of code. Another popular style puts the left brace on the next line. Here is the same example program formatted in this style:

There are people (including some authors of this book) who prefer this style because it’s easier to see where blocks of code begin and end. However, the other style uses less space, so we use it throughout the book. You can make your own choices about style, but be consistent! If you work for a software development company, they may have strict standards for code formatting.

As we mentioned before, you can leave comments in your code whenever you want someone reading the code to have extra information. Java has three different kinds of comments. We described single-line comments, which start with a // and continue until the end of the line.

If you have a large block of text you want as a comment, you can create a block comment, which starts with a /* and continues until it reaches a */.

Beyond leaving messages for other programmers, you can also “comment out” existing code. By putting Java code inside a comment, it no longer affects program execution. This practice is common when programmers want to remove or change some code but are reluctant to delete it until the new version of the code has been tested. Don’t overuse the practice of commenting out code! Large programs become hard to navigate when they’re cluttered with many chunks of commented-out code.

The third kind of comment is called a documentation comment and superficially looks a lot like a block comment. A documentation comment starts with a /** and ends with a */. These comments are supposed to come at the beginning of classes and methods and explain what they’re used for and how to use them. A tool called javadoc is used to run through documentation comments and generate an HTML file that users can read to understand how to use the code. This tool is a feature that has contributed greatly to the popularity of Java, keeping its libraries well-documented and easy to use. However, we do not discuss documentation comments deeply in this book.

Here is our example output program, heavily commented.

Comments are a wonderful tool, but clean code with meaningful variable names and careful use of whitespace doesn’t require too much commenting. Never hesitate to comment, but always ask yourself if there is a way to write the code so clearly that a comment is unnecessary.

A variable intended to hold integer values can be declared with any of the four types byte, short, int, or long. All of them are signed (holding positive and negative numbers) and represent numbers in two’s complement. They only differ by the range of values that each type can hold. These ranges and the number of bytes used to represent variables from each type are given below.

Note that the entire range of byte is included in that of short, of short in that of int, and so on. We say that short is broader than byte, int is broader than short, and long is broader than int.

A variable declared with type byte can only represent 256 different values, the integers in the range -128 to 127. Why use byte at all, then? Since a byte value only takes up a single byte, it can save memory, especially if you have a list of variables called an array, which we will discuss in Chapter 6. However, too narrow of a range will result in underflow and overflow. Java programmers are advised to stick with int for general use. If you need to represents values larger than 2 billion or smaller than -2 billion, use long. Once you’re an experienced programmer, you may occasionally use byte and short to save space, but they should be used sparingly and for a clear purpose.

Earlier, we said that variables had to match the type of literals you want to store into them. In the example above, we declared age with type byte and then stored 32 into it. What is the type of 32? Is it byte, short, int, or long? By default, all integer literals have type int, but they can be used with byte or short variables provided that they fit within the range. Thus, the following line causes an error.

If you want to specify a literal to have type long, you can append l or L to it. Thus, 42 is an int literal, but 42L is a long literal. You should always use the capital L since l can be difficult to distinguish from 1.

At the time of this writing, Java 11 is the newest version of Java, but Java 8 is most commonly used. In Java 7 and higher, you’re allowed to put any number of underscores (_) inside of numerical literals to break them up for the sake of readability. Thus, 123_45_6789 might represent a social security number, or you could use underscores instead of commas to write three million as 3_000_000. Since most compilers support Java 7 or higher now, it’s reasonable to use this underscore notation in your literals. Note that you should never use a comma in a numerical Java literal, no matter which version of Java you’re using.

To represent numbers with fractional parts, Java provides two floating-point types, double and float. Because of limits on floating-point precision discussed in Chapter 1, Java cannot represent all real or rational numbers, but these types provide good approximations. If you have a variable that takes on floating-point values such as 3.14, 1.707 × 10²⁵, 9.8, or similar, it ought to be declared as a double or a float.

As discussed in Chapter 1, integer types within their specified ranges have exact representations. For example, if you assign 19 to a variable of type int and then print this value, you always get exactly 19. Floating-point numbers do not have this guarantee of exact representation.

Variables of type float give you an accuracy of about 6 decimal digits while those of type double give about 15 decimal digits. Does the accuracy of floating-point number representation matter? The answer to this question depends on your application. In some applications, 6-digit accuracy may be adequate. However, when doing large-scale simulations, such as computing the trajectory of a spacecraft on a mission to Mars, 15-digit accuracy might be a matter of life or death. In fact, even double precision may not be enough. There is a special BigDecimal class which can perform arbitrarily high precision calculations, but due to its low speed and high complexity, it should only be used in those rare situations when a programmer requires a much higher level of precision than what double provides.

Java programmers are recommended to use double for general purpose computing. The float type should only be used in special cases where storage or speed are critical and accuracy is not. Because of its greater accuracy, double is considered a broader type than float. You can store float values in a double without losing precision, but the reverse is not true.

All floating-point literals in Java have type double unless they have an f or F appended on the end. Thus, 3.14 is a double literal, but 3.14f is a float literal.

Formatting output for floating-point numbers has an extra complication compared with integer output: How many digits after the decimal point should be displayed? If you’re representing money, it’s common to show exactly two digits after the decimal point. By default, all of the non-zero digits are shown.

Instead of using System.out.print(), you can use System.out.format() to control formatting. When using System.out.format(), the first argument to the method is a format string, a piece of text that gives all the text you want to output as well as special format specifiers that indicate where other data is to appear and how it should be formatted. This method takes an additional argument for each format specifier you use. The specifier %d is for integer values, the specifier %f is for floating-point values (including both float and double types), and the specifier %s is for text. Consider the following example:

The output of this code is

This kind of output is based on the printf() function used for output in the C programming language. It allows the programmer to have a holistic picture of what the final output might look like, but it also gives control of formatting through the format specifiers. For example, you can choose the number of digits for a floating-point value to display after the decimal point by putting a . and the number between the % and the f.

The output of this code is:

Note that the last visible digit is rounded instead of truncated. Note that %n is a special format specifier that indicates a newline. To learn about other ways to use format strings to manipulate output, read the Oracle Formatter documentation.

The following table lists the arithmetic operators available in Java. All of these operators can be used on both the integer primitive types and the floating-point primitive types.

The first four of these should be familiar. Addition, subtraction, and multiplication work as you would expect, provided that the result is within the range defined for the types you’re using, but division is a little confusing. If you divide two integer values in Java, you’ll get an integer as a result. If there would have been a fractional part, it will be truncated, not rounded. Consider the following.

In normal mathematics, 1,999 ÷ 1,000 = 1.999. In Java, 1999/1000 yields 1, and that’s what is stored in x. For floating-point numbers, Java works much more like normal mathematics.

In this case, y contains 1.999. The literals 1999.0 and 1000.0 have type double. The type of y does not affect the division, but it had to be double to be a legal place to store the result.

You may not have thought about this idea since elementary school, but the division operator (/) finds the quotient of two numbers. The modulus operator (%) finds the remainder. For example, 15 / 6 is 2 while 15 % 6 is 3 because 6 goes into 15 twice with 3 left over. The modulus operator is usually used with integer values, but it’s also defined to work with floating-point values in Java. It’s easy to dismiss the modulus operator because we don’t often use it in daily life, but it’s incredibly useful in programming. On its face, it allows us to see the remainder after division. This idea can be applied to see if a number is even or odd. It can also be used to compress a large range of random integers to a smaller range or perform a kind of circular arithmetic useful for cryptography. Keep an eye out for it. We’ll use it many times in this book.

Although all the previous examples use only one mathematical operator, you can combine several operators and operands into a larger expression like the following.

Such expressions are evaluated from left to right, using the standard order of operations: The * and / (and also %) operators are given precedence over the + and - operators. Like in mathematics, parentheses have the highest precedence and can be used to add clarity. Thus, the order of evaluation of a + b / c is the same as a + (b / c) but different from (a + b) / c.

All of the operators we’ve discussed so far are binary operators. This use of the word “binary” has nothing to do with base 2. A binary operator takes two things and does something, like adding them together. A unary operator takes a single operand and does something. The - operator can be used as a unary operator to negate a literal, variable, or expression. A unary negation has a higher precedence than the other operators, just like in mathematics. In other words, the variable or expression will be negated before it’s multiplied or divided. The + operator can be used anywhere you’d use a unary negation, although it doesn’t actually do anything. Consider the following statements.

Some operations happen frequently in Java. For example, increasing a variable by some amount is a common task. If you want to increase the contents of variable value by 10, you can write the following.

Although the statement above is not excessively long, increasing a variable is common enough that there’s shorthand for it. To achieve the same effect, you can use the += operator.

The += operator gets the contents of the variable, in this case value, adds whatever is on its right side, in this case 10, and stores the result back into the variable. Essentially, it saves you from writing the name of the variable twice. And += is not the only shortcut. It’s only one member of a family of shortcut operators that perform a binary operation between the variable on the left side and the expression on the right side and then store the value back into the variable. There’s a -= operator that decreases a variable, a *= operator that scales a variable, and several others, including shortcuts for bitwise operations we cover in the next subsection.

These assignment shortcuts are useful and can make a line shorter and easier to read.

There are also two unary shortcuts. Incrementing a value by one and decrementing a value by one are such common operations that they get their own special operators, ++ and --.

Using either an increment or decrement changes the value of a variable. In all other cases, the use of an assignment operator is required to change a variable. Even in the binary shortcuts given before, the programmer is reminded that an assignment is occurring because the = symbol is present.

Both the increment and decrement operators come in prefix and postfix flavors. You can write the ++ (or the --) in front of the variable you’re changing or behind it.

When used in a line by itself, either flavor works exactly the same. However, the incremented (or decremented) variable can also be used as part of a larger expression. In a larger expression, the prefix form increments (or decrements) the variable before the value is used in the expression. Conversely, the postfix form gives back a copy of the original value, effectively incrementing (or decrementing) the variable after the value is used in the expression. Consider the following example.

After the code is executed, the values of prefix and postfix are both 8. However, prefixResult is 13 while postfixResult is only 12. The original value of postfix, which is 7, is added to 5, and then the increment operation happens afterward.

In general it’s unwise to perform increment or decrement operations in the middle of larger expressions, and we advise against doing so. In some cases, code can be shortened by cleverly hiding an increment in the middle of some other expression. However, when reading back over the code, it always takes a moment to be sure that increment or decrement is doing exactly what it should. The additional confusion caused by this cleverness is not worth the line of code saved. Furthermore, the compiler will translate the operations into exactly the same bytecode, meaning that the shorter version is no more efficient than the longer version when executed.

Nevertheless, many programmers enjoy squeezing their code down to the smallest number of lines of code possible. You may have to read code that uses increments and decrements in clever (if obscure) ways, but you should always strive to make your own code as readable as possible.

In addition to normal mathematical operators, Java provides a set of bitwise operators corresponding to the operations we discussed in Chapter 1. These operators perform bitwise operations on integer values. The bitwise operators are &, |, ^, and ~ (which is unary). In addition, there are bitwise shift operators: << for signed left shift, >> for signed right shift, and >>> for unsigned right shift. There is no unsigned left shift operator in Java.

When used with byte and short, all bitwise operators will automatically convert their operands to 32-bit int values. It’s crucial to remember this conversion since the number of bits used for representation is a fundamental part of bitwise operators.

The following example shows these operators in use. In order to understand the output, you need to understand how integers are represented in the binary number system, which is discussed in Section 1.3.

Why use the bitwise operators at all? Sometimes you may read data as individual byte values, and you might need to combine four of these values into a single int value. Although the signed left shift (<<) and signed right shift (>>) are, respectively, equivalent to repeated multiplications by 2 or repeated divisions by 2, they’re faster than doing these operations over and over. Finally, some of these operations are used for cryptographic or random number generation purposes.

Sometimes you need to use different types (like integers and floating-point values) together. Other times, you have a value in one type but need to store it in another (like when you’re rounding a double to the nearest int). Some combinations of operators and types are allowed, but others cause compiler errors.

The guiding rule is that Java allows an assignment from one type to another, provided that no precision is lost. That is, we can copy a value of one type into a variable of another type, provided that the destination variable has a broader type than the source value. The next few examples illustrate how to convert between different numerical types.

In order to perform a downcast, the programmer has to mark that he or she intends for the conversion to happen. A downcast is marked by putting the result type in parentheses before the expression you want converted. The next example illustrates how to cast a double value to type int.

Numerical types and the conversions between them are critical elements of programming in Java, which has a strong mathematical foundation. In addition to these numerical types, Java also provides two other types that represent individual characters and Boolean values. We examine these next.

Sentences are made up of words. Words are made up of letters. Although we have discussed powerful tools for representing numbers in Java, we need a way to represent the letters and other characters we might find in printed text. Values with the char type are used to represent individual characters.

In the older languages of C and C++, the char type used 8 bits for storage. From Chapter 1, you know that you can represent up to 2⁸ = 256 values with 8 bits. The Latin alphabet, which is used to write English, uses 26 letters. If we need to represent upper- and lowercase letters, the 10 decimal digits, punctuation marks, and quite a few other special symbols, 256 values is plenty. However, people all over the world use computers and want to store text from their language written in their script digitally. Taking the Chinese character system alone, some Chinese dictionaries list over 100,000 characters!

Java uses a standard called UTF-16 encoding to represent characters. UTF-16 is part of a larger international standard called Unicode, which is an attempt to represent most of the world’s writing systems as numbers that can be stored digitally. Most of the inner workings of Unicode aren’t important for day-to-day Java programming, but you can visit the Unicode site if you want more information.

In Java, each variable of type char uses 16 bits of storage. Therefore, each character variable could assume any value from among a total of 2¹⁶ = 65,536 possibilities (although a few of these are not legal characters). Here are a few declarations and assignments of variables of type char.

We’re storing char literals into each of the variables above. Most of the char literals you’ll use commonly are made by typing the single character you want in single quotes ('), such a 'z'. These characters can be upper- or lowercase letters, single numerical digits, or other symbols.

The space character literal is ' ', but some characters are harder to represent. For example, a new line (the equivalent of pressing <enter>) is represented as a single character, but we can’t type a single quote, hit <enter>, and then type the second quote. Instead, the character to represent a new line is '\n', which we will refer to simply as a newline. Every char variable can only hold a single character. It appears that '\n' has multiple characters in it, but it doesn’t. The use of the backslash (\) marks an escape sequence, which is a combination of characters used to represent a specific difficult to type or represent character. Here is a table of common escape sequences.

Remember, everything inside of a computer is represented with numbers, and each char value has some numerical equivalent. These numbers are arbitrary but systematic. For example, the character 'a' has a numerical value of 97, and 'b' has a numerical value of 98. The codes for all of the lowercase Latin letters are sequential in alphabetical order. (The codes for uppercase letters are sequential too, but there’s a gap between them and the lowercase codes.)

Some Unicode characters are difficult to type because your keyboard or operating system has no easy way to produce the character. Another kind of escape sequence allows you to specify any character by its Unicode value. There are large tables listing all possible Unicode characters by numerical values. If you want to represent a specific literal, you type '\uxxxx' where xxxx is a hexadecimal number representing the value. For example, '\u0064' converted into decimal is 16 × 6 + 4 = 100, which is the letter 'd'.

If you’re new to programming, it may seem useless to have a type designed to hold only true and false values. These values are called Boolean values, and the logic used to manipulate them turns out to be crucial to almost every program. We use them to represent conditions in Chapter 4, Chapter 5, and beyond.

To store these truth values, Java uses the type boolean. There are exactly two literals for type boolean: true and false. Here are two declarations and assignments of boolean variables.

If we could only store these two literals, boolean variables would have limited usefulness. However, Java provides a full range of relational operators that allow us to compare values. Each of these operators generates a boolean result. For example, we can test to see if two numbers are equal, and the answer is either true or false. All Java relational operators are listed in the table below. Assume that all variables used in the Example column have a numeric type.

In addition to the relational operators, Java also provides logical operators that can be used to combine or negate boolean values. These are the logical AND (&&), logical OR (||), logical XOR (^), and logical NOT (!) operators.

All of these operators, except for NOT, are binary operators. Logical AND is used when you want your result to be true only if both the operands being combined evaluate to true. Logical OR is used when you want your result to be true if either operand is true. Logical XOR is used when you want your result to be true if one but not both of your operands is true. The unary logical NOT operator (!) results in the opposite value of its operand, switching true to false or false to true. Both the relational operators and the logical operators are described in greater detail in Chapter 4.