Introduction - Java Software Solutions: Foundations of Program Design - page 9

therefore can represent two possible items or situations. If we want to represent
the state of a light bulb (off or on), one bit will suffice, because we can interpret 0
as the light bulb being off and 1 as the light bulb being on. If we want to represent
more than two things, we need more than one bit.
Two bits, taken together, can represent four possible items because there are
exactly four permutations of two bits: 00, 01, 10, and 11. Suppose we want to
represent the gear that a car is in (park, drive, reverse, or neutral). We would need
only two bits, and could set up a mapping between the bit permutations and the
gears. For instance, we could say that 00 represents park, 01 represents drive, 10
represents reverse, and 11 represents neutral. In this case, it wouldn't matter if we
switched that mapping around, though in some cases the relationships between
the bit permutations and what they represent are important.
Three bits can represent eight unique items, because there are
eight permutations of three bits. Similarly, four bits can represent 16
items, five bits can represent 32 items, and so on. Figure 1.7 shows
the relationship between the number of bits used and the number of
items they can represent. In general, N bits can represent 2 N unique
items. For every bit added, the number of items that can be represented doubles.

KEY CONCEPT
There are exactly 2 N permutations of
N bits. Therefore, N bits can repre-
sent up to 2 N unique items.

1 bit 2 bits 3 bits 4 bits 5 bits

32 items 2 items 4 items 8 items 16 items

0
1

00
01
10
11

000
001
010
011
100
101
110
111

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

00000
00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111

10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111

FIGURE 1.7 The number of bits used determines the number
of items that can be represented