Powers of 2 and their unique representation in the binary system are the basis of a wide range of clever programming tricks. Let’s start with a fairly obvious one: In every positional number system, we can multiply a number by its radix by appending a single zero to its digits. For example, the
product of the decimal number 87 and its radix 10 is \(870\), and the product of the binary number \(1101_2\) and its radix 2 is \(11010_2\). This idea generalizes to multiplication by an integer power of the base, which corresponds to appending
multiple zero digits:
What happens if we try the same trick with negative numbers in two’s-complement representation? It turns out that appending \(k\) zeros is again equivalent to multiplying by \(2^k\):
We prove that this works for every negative number in two’s-complement representation at the end of this section.
The equivalent of appending zeros on paper is shifting bits in memory. We can therefore compute \(2n\) using the bit operation \(n\shl 1\), which moves all bits of \(n\) one place to the left and inserts 0 as the least significant bit:
value << 1; // multiply value by 2
Likewise, \(2^kn\) can be computed by shifting \(k\) places:
value << k; // multiply value by 2**k
If the result of value << k doesn’t fit into the requested number of bits, only the least significant bits of the result are retained. For example, the expression 256 << 31 produces 0 and not the correct result \(2^{39}\), which lies outside
the range of 32-bit integers.
Dividing by Powers of 2
If doubling can be implemented by shifting the bit pattern to the left, does halving correspond to shifting to the right? For positive integers this is indeed the case: Shifting one place to the right performs an integer division by 2 and shifting \(k\) places divides
by \(2^k\). For example, shifting the bit pattern of \(109\) one place gives us
The least significant bits that are shifted out are the remainder of the division. In the last example, we have \(109 = 13\cdot 8 + 5\), and the 3 least significant digits of \(1101101_2\) are indeed \(101_2=5\).
For negative integers, however, a simple right shift doesn’t produce the correct result. For example, if we shift the bit pattern of \(-24\) two places to the right, we obtain the bit pattern of \(58\), a number that is larger in magnitude and has the wrong sign:
Fortunately, it is possible to define a new shift operator “\(\asr \)”, also known as the arithmetic shift operator, that correctly divides both positive and negative numbers. The arithmetic shift \(n \asr k\) performs a normal right shift by \(k\) places and then fills the upper \(k\) bits with ones if \(n\) is negative. In the
case of \(-24\asr 2\), this extends the intermediate result \(111010_2\) to the correct 8-bit result:
Notice that the bit pattern \(111010\) of the intermediate result is the 6-bit representation of \(-6\), so you can think of the arithmetic shift as a normal shift followed by a sign extension as discussed in the previous section.
The arithmetic shift operator \(n\asr k\) performs what is called a floor division, which means that the result of dividing by \(2^k\) is rounded to the nearest smaller integer. We can express this mathematically using the floor operator \(\lfloor \cdot {}\rfloor \):
The \(k\) lowest bits of \(n\) that are discarded by the arithmetic right shift have a special significance as well: They form the remainder of the division
There are many applications in which we want to divide by a power of 2 and round the result up toward the next larger integer. This operation is usually expressed using the ceiling operator \(\lceil \cdot \rceil \):
(Box 5.2 explains why this operation is useful in practice.) Can we implement this operation using bit shifts as well?
Let’s compare these two rounding modes when dividing by 4. First, here is \(\lfloor n/4\rfloor \) for a few small values of \(n\):
The ceiling operator \(\lceil n/4\rceil \) produces the same result if \(n\) is evenly divisible by 4, but it rounds up to the next integer otherwise:
Comparing these two diagrams makes it clear that the two functions are closely related: In both cases, exactly four integers in the top row are mapped to a particular quotient in the bottom row. The only difference is that the upper row is offset by \(-3\) in the case of the ceiling operator (for example, the numbers that are mapped to 0 are \(0,1,2,3\) for the floor operator and \(-3,-2,-1,0\) for the ceiling). This means that we can compute \(\lceil n/4\rceil \) adding 3 to the input and then performing a floor division, and for an arbitrary power of 2, we have
For fixed values of the exponent \(k\) this trick is often used as an inline expression; for instance, (x + 7) >> 3 performs a division by 8 rounded up to the nearest integer.
Trailing Zeros
The bit patterns of even numbers end with a 0 and those of odd numbers with a 1. Here are a few examples of even numbers
and of odd numbers
We can therefore check whether a number is even or odd by inspecting its least significant bit:
In both functions the rightmost bit of value is isolated using the expression value & 1.
This is a special case of a more general property of numbers in two’s-complement representation: The number of trailing zeros indicates how often a number is evenly divisible by 2: If a number has a single trailing zero, it is divisible
by 2; if it has two trailing zeros, it is divisible by 4; if it has three trailing zeros, it is divisible by 8; and so on. This works for positive as well as negative integers:
We can use this observation to round down any integer \(x\) to the nearest multiple of \(2^k\) by clearing its \(k\) least significant bits. Mathematically, this can be expressed as follows: To round to the next smaller multiple of \(2^k\), we first divide by \(2^k\), then round to
the nearest smaller integer using the floor operator, and finally scale the result back to the original range:
We can define a similar operation for rounding to the next greater multiple of \(2^k\) by replacing the floor operator with the ceiling operator \(\lceil \cdot \rceil \):
For fixed values of the exponent \(k\) this trick is often used as an inline expression; for instance, (x + 0b11) & ~0b11 rounds up to the nearest multiple of 4.
Box 5.2: Partitioning MemoryPrograms that work with large amounts of data — including operating systems, databases, or image processing applications — often have to
partition this data into smaller fixed-size chunks that can be stored or processed independently. Bit tricks can simplify and speed up this kind of partitioning.
Let’s say the original data consists of \(N=22\) items, which we split into chunks of size \(M=8\). This results in two full chunks of size 8 and one final chunk that contains the remaining 6 items:
With this kind of partioning, we replace the single index \(i\) in the original data with a double index \((c,p)\), where \(c\) is the index of the chunk and \(p\) the position inside the chunk. It’s easy to convert between these two addressing modes:
\(\seteqnumber{0}{5.}{6}\)
\begin{gather*}
i=cM+p,\qquad c=\lfloor i/M\rfloor ,\qquad p=i\bmod m
\end{gather*}
The total number of chunks is \(\lceil N/M\rceil \) and the final chunk contains \(N-\lfloor N/M\rfloor M\) items.
If we make the size of each such chunk a power of 2, say \(M=2^e\), all the divisions and multiplications can be replaced with bit operations:
.
Quantity
Arbitrary \(M\)
\(M=2^e\)
chunk that contains index \(i\)
\(\lfloor i/M\rfloor \)
\(i \asr e\)
position of index \(i\) inside chunk
\(i\bmod M\)
\(i \AND (M-1)\)
first index in chunk \(c\)
\(mc\)
\(c \shl e\)
number of complete chunks
\(\lfloor N/M\rfloor \)
\(N\asr e\)
number of chunks
\(\lceil N/M\rceil \)
\((N + M-1)\asr e\)
items in final incomplete chunk
\(N\bmod M\)
\(N \AND (M-1)\)
Because these operations are so efficient, computer memory is almost always measured in powers of 2: A byte consists of 8 bits, a long integer of 8 bytes, and operating systems divide the computer’s RAM into pages of \(4096=2^{12}\) bytes, and so on.
Even the size of physical RAM modules is generally measured in powers of 2, from \(2^{20}\) bytes (MiB) to \(2^{30}\) bytes (GiB).
Leading Zeros and Logarithms
In this section we will discuss one last quantity that is derived from the bit pattern of a number \(n\): the number of leading zeros \(\text {nlz}(n)\). This quantity is only defined for numbers that are stored in a fixed number of bits and counts the number of zeros to the left of the most significant bit. Here are a few examples:
For negative numbers the number of leading zeros is 0 since the leftmost bit is always set in two’s-complement representation. But for nonnegative integers there is an interesting pattern: For \(w\)-bit integers, the function starts at \(\text {nlz}(0)=w\) and then
decreases by 1 every time we reach a new power of 2. The following table shows the value for the 8-bit integers in Fig. 5.5:
.
\(n\)
1
\(2\isep 3\)
\(4\isep 7\)
\(8\isep 15\)
\(16\isep 31\)
\(32\isep 63\)
\(64\isep 127\)
\(\text {nlz}(n)\)
7
6
5
4
3
2
1
The reason is obvious: Every time we reach a new power of 2, an additional binary digit is needed, which in turn reduces the number of leading zeros by 1.
It’s therefore no surprise that the number of leading zeros of a number \(n\) is closely related to its binary logarithm \(\log _2 n\), in particular the integer part \(\lfloor \log _2 n\rfloor \). Figure 5.6 compares these three functions for 8-bit integers. It’s easy to see
that the number of leading zeros is inversely related to \(\lfloor \log _2 n\rfloor \):
This is a simple way to compute the integer part of the base-2 logarithm without having to resort to floating point arithmetic.
Figure 5.6 The nlz function compared to the binary logarithm.
We can find a similar trick for computing the binary logarithm rounded to the next larger integer by comparing \(\lfloor \log _2 n \rfloor \) and \(\lceil \log _2 n \rceil \) for a few small values of \(n\):
The special case for \(n=1\) disappears because \(\text {nlz}(0)=w\). The ceiling of \(\log _2\) is particularly useful in practice because it lets us round a positive integer \(n\) to the nearest power of 2 that is at least as large as \(n\), which can be
expressed as \(2^{\lceil \log _2 n\rceil }. \) We will discuss an application in Section 10.2.
Functions that implement these two variations of the binary logarithm are shown in Listing 5.4. The first function floorBinaryLog() computes \(\lfloor \log _2 n\rfloor \) using Eq. (5.7) and the second function ceilBinaryLog() computes \(\lceil \log _2 n\rceil \) using Eq. (5.8).
Listing 5.4ch5 / IntMath
// Compute the binary logarithm, rounded down.
public static int floorBinaryLog(int value) {
if (value < 1)
throw new ArithmeticException("log of number <= 0");
return 31 - Integer.numberOfLeadingZeros(value);
}
// Compute the binary logarithm, rounded up.
public static int ceilBinaryLog(int value) {
if (value < 1)
throw new ArithmeticException("log of number <= 0");
return 32 - Integer.numberOfLeadingZeros(value - 1);
}
Exercise 5.7.What does the expression (x << 1) | 1 compute, assuming that x is of type int?
Exercise 5.8.What is the result of -1 >>> k and -1 >> k?
Exercise 5.9.On binary computers, integer multiplications by positive constants can sometimes be implemented more efficiently by replacing them with a combination of bit shifts and additions. The
expression \(15x\), for instance, can implemented as
(x << 3) + (x << 2) + (x << 1) + x
Explain why this trick works and how to compute \(298x\) using bit shifts and additions. Bonus question: Can you compute \(15x\) using fewer shifts or additions?
