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