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