2013
11-12

# Expectation

Eric has constructed an easy scheme for generating random integer numbers. His scheme inputs an integer n and generates evenly distributed random integer value between 0 and (n − 1) inclusive. For example, if n = 3, the scheme generates 0, 1 or 2, each with probability 1/3.

Now Eric is planning to construct more complicated schemes. The first one will consist of two independent random generators with their outputs forwarded to his favorite XOR gate, which does bitwise exclusive or with its two inputs.

Eric’s friend Nick studies math. Nick said that the scheme is very interesting, and the most interesting thing is the expectation of the result. Now they both think how to calculate the expectation. Could you help them?

Remember that the expectation of the random variable is its average value. For a variable ξ with nonnegative integer values it can be calculated as

,

where pi is the probability of ξ being equal to i.

The first line of the input contains the number k of cases to solve (1 ≤ k ≤ 1 000). Each case consists of a single integer 1 ≤ n ≤ 109 on a separate line.

For each case output the expected value of the new Eric’s scheme with at least two digits after the decimal point. Output each result on a separate line.

2
3
4

1.33
1.50

/* @author: */
import java.util.*;
import java.io.*;
import java.lang.reflect.Array;

public class Main {
static public void main( String [] string ) throws Exception{
Scanner cin = new Scanner( System.in );
int m = cin.nextInt();
int n, i, p1, p0, s;
double v;
while( (m--) > 0 ) {
s = n = cin.nextInt();
v = 0;
for( i=1; i< n; i<<=1 ) {
if( (s&1) == 1 ) {
p0 = (s/2+1)*i;
p1 = n-p0;
}
else {
p1 = s/2*i;
p0 = n-p1;
}
v += i*(2.0*p1/n*p0/n);
s >>= 1;
}
System.out.printf( "%.2f\n", new Object[]{ Double.valueOf(v) } );
}
return;
}
}

1. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.