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