Integer types such as int and long can be interpreted in two ways: as small containers of bits that hold binary data and as ordinary integers that can be added, multiplied, and compared to each other. In this section we take a closer look at the
interplay between bit patterns and the numbers they represent.
Two’s-Complement Representation
Computers typically store signed integers in a variation of the binary system known as two’s-complement representation. In this representation, positive integers are stored as ordinary binary numbers, whereas negative numbers are stored in complemented form. Figure 5.3 illustrates how this works in the case of 8-bit integers. The left part of the image shows the bit patterns of nonnegative integers between 0 and 127, which are stored as binary numbers between \(00000000_2\)
and \(01111111_2\). The right part shows the bit patterns of negative integers between \(-1\) and \(-128\). Here, each number \(n\) is stored as the binary number \(256+n\), which produces bit patterns between 10000000 and 11111111.
Figure 5.3 Bit patterns of signed integers in two’s-complement representation.
Example5.1. The 8-bit representation of 72 is 01001000 because
These ideas readily generalize to integers with any number of bits such as 32-bit and 64-bit integers. In the case of \(w\)-bit integers, we have \(2^w\) different bit patterns to work with. The bit patterns are split into two halves, one for nonnegative and one for negative numbers:
.
range
bit patterns
nonnegative
0 to \(2^{w-1}-1\)
\(000\dots 000\) to \(011\dots 111\)
negative
\(-2^{w-1}\) to \(-1\)
\(100\dots 000\) to \(111\dots 111\)
Here are the general rules for converting between numbers and their bit patterns:
•Integer \(n\) to bit pattern — If \(n\) is nonnegative, the corresponding bit pattern is the binary representation of \(n\); if \(n\) is negative, it is the binary representation of \(2^w+n\).
•Bit pattern to integer — First interpret the bit pattern as an unsigned integer \(x\). If \(x<2^{w-1}\), the bit pattern represents the nonnegative number \(x\); otherwise, it represents the negative number \(x-2^w\).
Notice that the most significant (leftmost) bit is always 0 for nonnegative and 1 for negative numbers. Since the number zero takes up one slot in the positive half of bit patterns, the range of negative integers is one larger than the range of positive integers. For the
standard integer types this gives us the ranges shown in Fig. 5.4.
.
Type
Bits
Smallest Value
Largest Value
byte
8
−128
127
short
16
−32 768
32 767
int
32
−2 147 483 648
2 147 483 647
long
64
−9 223 372 036 854 775 808
9 223 372 036 854 775 807
Figure 5.4 Numerical range of Java integer types.
There is an interesting relationship between each number \(n\) and its negation \(-n\) in two’s-complement representation, which you can find by comparing the two columns in Fig. 5.3: For a positive number \(n\) in the left column, the bit pattern of \(-n\) if obtained by moving up one row and switching to the right column — in other words, by subtracting 1 and then inverting the bit pattern:
Similarly, for a negative number \(n\) in the right column, the bit pattern of \(-n\) is obtained by moving down one row and switching to the left column, which also corresponds to subtracting 1 and inverting the bit pattern. Finally, you can convince yourself that the relationship in
Eq. (5.1) also holds for \(n=0\).
What does Eq. (5.1) compute if \(n\) is the smallest negative integer \(n=-2^{w-1}\)? In this case, both sides of the equation produce a number
that lies outside of the allowed range — both computations are said to overflow. However, all modern computers define integer overflow in such a way that both sides evaluate to the same bit pattern, so that Eq. (5.1) holds for all \(w\)-bit integers. We will have more to say about integer overflow in Chapter 11.
It’s also instructive to consider how the bit patterns in two’s-complement representation change depending on the bit width \(w\), the number of bits used to store the number. For positive integers., the bit pattern is always the binary
representation extended to \(w\) bits, so the number \(87=1010111_2\) has the following 8-, 16-, and 32-bit representations:
.
01010111
8 bits
0000000001010111
16 bits
00000000000000000000000001010111
32 bits
For negative negative numbers such as \(-17\), we find the bit pattern by adding \(2^w\) and converting the result to binary. For 8-, 16-, and 32-bit integers this gives us \(2^8-17=239\), \(2^{16}-17=65\,519\), and \(2^{32}-17=4\,294\,967\,279\), which results in the following bit patterns:
.
11101111
8 bits
1111111111101111
16 bits
11111111111111111111111111101111
32 bits
In this case, the bit patterns are extended with ones instead of zeros.
In general, increasing the bit width fills the upper bits of negative integers with ones and those of nonnegative integers with zeros. This is what happens when converting a small integer type such as byte or short to a larger integer type such as
int or long. The process is also referred to as sign extension since the new bits are always filled with the most significant bit of the original value, which, as we saw, indicates the sign of the number. To convert a number to a representation with fewer bits, we simply throw away the
most significant bits; this is what happens when converting from a large integer type to a smaller one.
Now that we understand the basics of two’s-complement representation, let’s take a closer look at the resulting bit patterns and see if we can find any interesting patterns. We will focus on 8-bit integers between \(-128\) and \(127\) (Fig. 5.5), but everything we will discuss in the following applies to other integer types as well.
Figure 5.5 The bit patterns of 8-bit integers between -128 and 127 in two’s-complement representation.
• The bit pattern of 0 consists of zeros only, and the bit pattern of \(-1\) of ones:
Many simple bit patterns that consist of a single run of ones can be constructed by starting with the constant \(-1\) and then shifting the bit pattern to the left or right as required. Here are a few examples:
int allBits = -1; // 0xffffffff
int highest24Bits = -1 << 8; // 0xffffff00
int lowest8Bits = -1 >>> 24; // 0x000000ff
int allExceptLowest = -1 << 1; // 0xfffffffe
int allExceptHighest = -1 >>> 1; // 0x7fffffff
• Numbers of the form \(2^k\), namely \(1, 2, 4, 8, \dots \), have a bit pattern that consists of a single 1 followed by \(k\) zeros.
Any power of \(2\) can therefore be computed by shifting a single bit \(k\) places to the left:
int powerOfTwo = 1 << k;
• For all numbers of the form \(2^k-1\), namely \(0, 1, 3, 7, \dots \), the bit pattern consists of exactly \(k\) ones in the least significant bits:
Since numbers of the form \(2^k\) can be written as 1 << k, we can compute a bit pattern whose lowest \(k\) bits are 1 as follows:
int kLowestBitsSet = (1 << k) - 1;
(The parentheses are necessary because the shift operator “<<” has a higher precedence than the minus operator.)
• Numbers of the form \(-2^k\), namely \(-1, -2, -4, \dots \), have bit patterns that consist of \(k\) zeros in the rightmost bits and ones everywhere else:
We can use this observation to clear the lowest \(k\) bits of a given value:
int lowestBitsCleared = value & -(1 << k);
Exercises
Exercise 5.5.Explain why the \(w\)-bit representation of \(-1\) always consists of \(w\) consecutive 1-bits in two’s-complement representation.
Exercise 5.6.Consider a hypothetical computer that stores its numbers as 10-bit integers using two’s-complement representation. What is the range
of numbers that can be stored in this format? Fill in the missing entries in the following table:
