Expectation

Eric has developed a simple scheme for generating random integers. This scheme takes an integer $n$ as input and uniformly generates integers from $0$ to n - 1, inclusive. For example, if n = 3, the scheme generates each of the numbers $0$, $1$, or $2$ with equal probability $1/3$.

Now Eric wants to create more complex schemes. The first of them consists of two independent random number generators whose outputs are combined using the bitwise $XOR$ operation — exclusive OR.

Eric's friend Nick, who studies mathematics, noted that this scheme is quite interesting, and what's even more interesting is its expected value. Help them compute it.

Recall that the expected value of a random variable is defined as its average value. For a random variable $\xi$ taking non-negative integer values, it is computed using the formula:

where p_i is the probability that ξ = i.