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