A well-known technique for computing x^{n}, when n
is a nonnegative integer, involves the binary representation of n. The technique applies to the evaluation of an
expression of the form x ?x ?x ?x ???x where ?is
any associative operation, such as addition, multiplication including matrix
multiplication, and string concatenation (as suggested by the notation ('ab')^{3}
= 'ababab'). As an example, suppose we wish to compute y = x^{13}. Because
13 expressed in binary is 1101 (that is, 13 = 8 + 4 + 1),

Thus, x^{13}
may be computed as follows:

This requires five multiplications, considerably fewer than the 12 that would be required by repeated multiplication by x.

If the exponent is a variable, known to be a nonnegative integer, the technique can be employed in a subroutine, as shown in Figure 11-6.

`int iexp(int x, unsigned n) {`

`牋 int p, y; `

` `

`牋 y = 1;牋牋牋牋牋牋牋牋牋牋 // Initialize result `

`牋爌 = x;牋 牋牋牋牋牋牋牋牋牋// and p. `

`牋爓hile(1) {`

`牋牋?if (n & 1) y = p*y;牋牋 // If n is odd, mult by p. `

`牋牋牋n = n >> 1;牋牋牋牋牋牋 // Position next bit of n. `

`牋牋牋if (n == 0) return y;牋 // If no more bits in n. `

`牋牋牋p = p*p;牋牋牋牋牋牋牋?// Power for next bit of n. `

`牋爙 `

`} `

The number of multiplications done by this method is, for exponent n 1,

This is not always the minimal number of multiplications. For example, for n = 27 the binary decomposition method computes

which requires seven multiplications. However, the scheme illustrated by

requires only six. The smallest number for
which the binary decomposition method is not optimal is n =15 (hint: x^{15}
= (x^{3})^{5}).

Perhaps surprisingly, there is no known
simple method that, for all n, finds an optimal
sequence of multiplications to compute x^{n}.
The only known methods involve an extensive search. The problem is discussed at
some length in [Knu2, sec. 4.6.3].

The binary decomposition method has a variant that scans the binary representation of the exponent in left-to-right order [Rib, 32], which is analogous to the left-to-right method of converting binary to decimal. Initialize the result y to 1, and scan the exponent from left to right. When a 0 is encountered, square y. When a 1 is encountered, square y and multiply it by x. This computes as

It always requires the same number of (nontrivial) multiplications as the right-to-left method of Figure 11-6.

The IBM XL Fortran compiler takes the definition of this function to be

It is assumed that n
and the result are interpreted as signed integers. The ANSI/ISO Fortran
standard requires that the result be 0 if n
< 0. The definition above for n 31
seems reasonable in that it is the correct result modulo 2^{32}, and it
agrees with what repeated multiplication would give.

The standard way to compute 2^{n} is to put the integer 1 in a register
and shift it left n places. This does not
satisfy the Fortran definition, because shift amounts are usually treated
modulo 64 or modulo 32 (on a 32-bit machine), which gives incorrect results for
large or negative shift amounts.

If your machine has number of leading zeros, pow2(n) may be computed in four instructions as follows [Shep]:

The shift right operations are "logical" (not sign-propagating), even though n is a signed quantity.

If the machine does not have the "nlz" instruction, its use above can be replaced with one of the x = 0 tests given in "Comparison Predicates" on page 21, changing the expression A possibly better method is to realize that the predicate 0 x 31 is equivalent to and then simplify the expression for given in the cited section; it becomes ?span class=docemphbolditalic1>x & (x - 32). This gives a solution in five instructions (four if the machine has and not):