Java Reference

In-Depth Information

and

n/2 = d
k-1
*2
k-2
+ ... + d
1
*2
0

Therefore, the binary representation of
n
is:

the binary representation of
n/2
followed by the bit
n%2.

We can then find the next bit
d
1
in the same way from
n/2
. This gives us the

idea for a loop invariant. We introduce a variable
x
and use the invariant:

invariant: the binary representation of
n
is:

the binary rep. of
x
followed by the reverse of
d[0..k-1]

The function is in Fig. III.2. Initially, we don't know how many bits there are in

the representation of
n
. Therefore, an array of the largest size possible is created

and used. We know the maximum size,
31
, because the parameter is an
int
.

Then, at the end of the function body, we create an array of the right size and

copy the digits into this new array. Note that if
n=0
, then
k=0
at the end, and

we are creating an array of
0
elements and copying
0
elements into it.

Converting from base 2 to an int

In Fig. III.3, we present a function to compute
n
from its binary representa-

tion in an array. The value of
n
is given by:

n =
∑
i in 0..d.length-1
d[i]*2
i

The formula for
n
is a polynomial whose coefficients are in array
d
, and
n
is most

efficiently calculated using a method called
Horner's scheme
. To see this

scheme, write the polynomial as:

d[0] * 2
0
+ d[1] * 2
1
+ d[2] * 2
2
+ … + d[3] * 2
3
+ …

and factor out multiples of
2
:

d[0] + 2 * (d[1] + 2 * (d[2] + 2 * (d[3] + …)))

/** =
the integer whose binary representation is in array
d */

public static int
BinaryToInt(
int
[] d) {

int
x= 0;

int
k= d.length;

// inv: 0 <= k <= b.length
and

// x = d[k] + 2*(d[k + 1] + 2 * (d[k + 2] + 2 * (d[k + 3] + …)))

while
(k != 0) {

k= k - 1;

x= x * 2 + d[k];

}

return
x;

}

Figure 1II.3:

Function
BinaryToInt

Search WWH ::

Custom Search