The beauty of a living thing
is not the atoms that go into it,
but the way those atoms are put together.
— Carl Sagan, Cosmos
Everything a computer does — every computation it performs, every decision it makes, and every piece of data it stores or transmits — involves reading, writing, or manipulating bits. A single bit is utterly unremarkable: It has two
different states one/zero, true/false, or on/off, and the only “computation” we can perform on a single bit is to flip its value from zero to one and vice versa. It’s only when you take groups of bits that things become interesting. With two bits we can already distinguish between four different
states, which is enough to define logical operators such as AND, OR, and NOT. With four bits we can store decimal digits and define simple arithmetic operations. Eight bits are enough to store the characters of the Latin alphabet and construct simple microprocessors. And the computer on your desk and
the smartphone in your pocket demonstrate what is possible with a few billion bits: You can store basically any kind of information and perform almost any computation imaginable — at least in theory.
In this chapter we will discuss a wide range of programming techniques for computing with bits.
Bits are conventionally stored and processed in groups of 8, 16, 32, or 64 bits. A group of 8 bits is known as a byte, but no standardized terms exist for groups of 16, 32, and 64 bits. Instead, every programming environment and processor manufacturer has its own nomenclature, and a 32-bit quantity may be called a word, doubleword, longword,
int, or a long. To avoid confusion, we will call a group of \(w\) bits a \(w\)-bit word or a \(w\)-bit integer. Fortunately, the situation is comparatively easy in Java, where the four integer typesbyte, short,
int, and long are guaranteed to have exactly 8, 16, 32, and 64 bits.
The easiest way to specify bit sequences is to use binary numbers. For example, the following listing initializes the variables a, b, and c with bit sequences of length 8, 16, and 32:
byte a = (byte) 0b01010101;
short b = (short) 0b110011001100110011;
int c = 0b11001100110011001110101011010101
The type casts in the first two lines are necessary because binary constants in Java are always considered 32-bit integers.
As a more interesting example, consider the image shown in Fig. 5.1, which shows a black-and-white image of the ten decimal digits. If we represent every black pixel as a ones and every white pixel as a zeros, we can store such images very compactly
in two-dimensional arrays of bits. Such bitmap images were widely used in the earlier days of computing, when display resolutions were low and memory scarce, and they still have many applications ranging from LED displays to retro games.
Figure 5.1 Bitmap representation of the decimal digits.
All digits have a height of 8 pixels, but their widths vary from three pixels for the digit 1 to seven pixels for 4; all other digits are six pixels wide. If we pack the digits right next each other, we can fit the entire image into \(58\times 8\) pixels, so we can store it in eight
long integers (Listing 5.1).
Box 5.1: Hexadecimal NumbersBecause binary numbers can become long and unwieldy, bit sequences are often written as hexadecimal (base-\(16\)) numbers to make them more compact.
Hexadecimal numbers use 16 digits: the ten decimal digits 0 to 9 and the first six letters of Latin alphabet A to F (in either upper- or lower-case). Translating between binary and hexadecimal numbers is easy because
groups of four binary digits correspond to exactly one hexadecimal digit and vice versa:
.
Decimal
0
1
2
3
4
5
6
7
Hexadecimal
0
1
2
3
4
5
6
7
Binary
0000
0001
0010
0011
0100
0101
0110
0111
Decimal
8
9
10
11
12
13
14
15
Hexadecimal
8
9
A
B
C
D
E
F
Binary
1000
1001
1010
1011
1100
1101
1110
1111
For example, to obtain the binary representation of 0xC0D3, we look up the bit patterns of C, 0, D, and 3 separately to obtain
Conversely, we can convert binary numbers to hexadecimal by splitting bits into groups of four (from the right) and replacing each quadruplet of bits with the corresponding hexadecimal digit. Translating between hexadecimal and binary constants is particularly easy if the bit
patterns consist of long runs of ones and zeros, which correspond to runs of F’s and zeros, respectively:
static int allBits = 0xffffffff;
static int highest24Bits = 0xffffff00;
static int lowest8Bits = 0x000000ff;
static int allExceptLowest = 0xfffffffe;
static int allExceptHighest = 0x7fffffff;
What can we do with the bitmap image stored in digitsImage? First of all, we can print the entire image to the screen by iterating over the bits of each row, as shown in Listing 5.2. The outer loop iterates over the rows and the inner loop over the 64 bits of each row, starting with the leftmost bit at position 63 and ending with the rightmost bit at index 0. The expression row & (1L << i) tests whether the \(i\)th bit of row is 1 or 0. It works as follows: We first use a bit shift “<<” to create a bit pattern that consist of a single 1-bit at
the \(i\)th position, counted from the right. The AND operator “&” is then used to clear all bits in row except the one we are interested in; the resulting integer is nonzero if this bit is 1 and zero otherwise. Printing the image in
digitsImage produces the following output:
XXXX XX XXXX XXXXXX XX XXXXXX XXX XXXXXX XXXX XXXX
XX XXXXXX XX XX XXX XX XX XXXX XXXX XX
XX XX XX XX XX X XX XX XX XXXX XXXX XX
XX XX XX XX XXXX X XX XXXXX XXXXX XX XXXX XX XX
XX XX XX XX XXX XX XXXX XX XX XX XX XXXXX
XX XX XX XX XXXXXXXXX XXXX XX XX XX XX XX
XX XX XX XX X XX XX X XXXX XX XX XX XX XX
XXXX XXXXXXXX XXXX XX XXXX XXXX XX XXXX XXX
Listing 5.2ch5 / BitmapFont
public static void printImage(long[] image) {
for (long row : image) {
for (int i = 63; i >= 0; i--) {
long bit = row & (1L << i);
System.out.print(bit != 0 ? 'X' : ' ');
}
System.out.println();
}
}
More generally, an expression of the form x & m keeps those bits of first argument x that are indicated by the bit pattern of the second argument m. For example, the expression x & 0b10101010 keeps the bits at
positions 1, 3, 5, and 7, whereas x & 0b11100 keeps those at positions 2, 3, and 4. A bit pattern that is 1 at certain positions of interest and 0 everywhere else is also called a bit mask.
As a more interesting example of bit masks, let us implement a function drawNumber() that uses the bitmap font defined above to draw an arbitrary decimal number. For example, calling drawNumber("3141592653") should
produce a bitmap image that contains the first 10 digits of \(\pi \):
XXXXXX XX XX XX XXXXXX XXXX XXXX XXX XXXXXX XXXXXX
XX XXX XXX XXX XX XX XX X XX XX XX XX
XX XX X XX XX XX XX XX XX XX XX XX
XXXX XX X XX XX XXXXX XX XX XX XXXXX XXXXX XXXX
XX XX X XX XX XX XXXXX XX XX XX XX XX
XX XX XXXXXXX XX XX XX XX XX XX XX XX
X XX XX XX XX X XX XX XX XX XX X XX X XX
XXXX XX XX XX XXXX XXX XXXXXX XXXX XXXX XXXX
The return value of drawNumber() is an array of eight 64-bit integers, one for each row of the resulting image.
The implementation of this function is shown in Listing 5.3. To be able to access the bits that belong to a certain digit, we store its width and position inside digitsImage in two auxiliary arrays width[] and position[]. The width of each digit is measured in pixels (or bits) and its position is the number of pixels to its right. Since the digits are placed right next to each other in digitsImage, each value in position[] is obtained by adding all later entries in width[]; for example, the position of the digit 4 is 30 since the digits 5,6,7,8,
and 9 are all six pixels wide. We use these two array to extract bits from digitsImage and combine them into a new image. The outer loop of drawNumber() iterates over the decimal digits to be drawn, and the inner loop copies each digit’s pixels from digitsImage into
result.
Listing 5.3ch5 / BitmapFont
static int[] width = {6, 3, 6, 6, 7, 6, 6, 6, 6, 6};
static int[] position = {52, 49, 43, 37, 30, 24, 18, 12, 6, 0};
public static long[] drawNumber(String num) {
long[] result = new long[digitsImage.length];
for (int i = 0; i < num.length(); i++) {
int digit = Character.getNumericValue(num.charAt(i));
for (int row = 0; row < result.length; row++) {
long pixels = (digitsImage[row] >>> position[digit])
& (1L << width[digit]) - 1;
result[row] = (result[row] << width[digit] + 1) | pixels;
}
}
return result;
}
Inside the loop, we first extract the relevant bits from digitsImage by shifting each row position[digit] places to the right and then
applying a bit mask to isolate the lowest remaining width[digit] bits. As we will discuss in the following section, the expression (1 << n) - 1 produces a bit mask that consists of exactly \(n\) ones in the
lowest (rightmost) bits. The bits extracted from digitsImage are then drawn to result[] by shifting the current row width[digit] + 1 places to the left
and then using a bitwise OR operation to combine the two bit patterns.
Exercises
Exercise 5.1. A simple text-based file format for exchanging bitmap images is the Portable Bitmap or simply PBM format. Figure 5.2 illustrates how the PBM format encodes a small image of \(11\times 8\) pixels. The first line always contains the marker P1, the second line the width and height of the image, and all the remaining lines
encode the image itself. Write a function that outputs the bitmap image stored in an array of long integers as a PBM file.
Exercise 5.2.A bit rotation moves bits to the left or to the right, like a normal bit shift, but bits that are shifted out on one end are re-inserted at the other. We use the functions rotl and rotr to denote
rotations to the left and right, respectively. For example, rotating the 32-bit pattern 0b10010111000000000000000000011111 ten places to the left produces
Use regular bit shifts and other bit operations to implement two functions rotl() and rotr() that rotate the bits of an int by a certain number of places.
Exercise 5.3.Consider the following bit patterns:
Each image has a size of \(8\times 8\) pixels and can be stored in a single 64-bit integer. Compute \(\NOT A\), \(\NOT B\), \(A\OR B\), \(A\AND B\), and \(A\XOR B\).
Exercise 5.4. Write a function that reverses the bytes in an integer. For example, the integer 0xCAFEF00D should be converted to
0x0DF0FECA. Can you perform this byte reversal using only eight bit operations?
