Java Reference
In-Depth Information
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 .
III.2
Base-2 logarithms
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
3.5849625007211565... because:
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.
integer
as a power of 2
in binary
logarithm
2 0
1
1
0
2 1
2
10
1
2 2
4
100
2
2 3
8
1000
3
2 4
16
10000
4
Figure 1II.4:
Powers of 2 and their logarithms
Search WWH ::

Custom Search