Now, we can compute this formula from the inside out, maintaining always the
following value x , for some k :
x = d[k] + 2* (d[k+1] + 2 * (d[k+2] + 2* (d[k+3] + …)))
The elements of d that appear in this formula are d[k..d.length-1] . If k=
d.length , no elements of d are involved in the sum, and x is 0 .
Figure III.4 contains the first five powers of two. The first column gives the inte-
gers in base 10; the second column, the integers written as a power of two; and
the third column, the integers written in binary. You can see a general rule for
writing powers of two in binary: the integer 2 n is 1 followed by n zeros.
For a positive integer 2 n , n is called the base-2 logarithm of n , written log 2
n , or, when it is clear from the context, simply as log n . The last column of Fig.
III.4 gives the logarithms of the first five powers of 2.
We can define logarithm in another way:
For an integer k = 2 n , log k is the number of times you have to
multiply 2 by itself to get k .
We have described logarithms using examples that were powers of 2 , but
log k is defined for any positive number k . For example: log 12 is
12 = 2 3.5849625007211565...
However, in this topic, we never require calculation of logarithms of arbitrary
numbers, and if you understand logarithms only for powers of 2, that is fine.
as a power of 2
Powers of 2 and their logarithms