---

Problem 323

---

Bitwise-OR operations on random integers

Let y₀, y₁, y₂,… be a sequence of random unsigned 32 bit integers
(i.e. 0 ≤ y_i < 2³², every value equally likely).

For the sequence x_i the following recursion is given:

• x₀ = 0 and
• x_i = x_i-1 | y_i-1, for i > 0. ( | is the bitwise-OR operator)

It can be seen that eventually there will be an index N such that x_i = 2³² -1 (a bit-pattern of all ones) for all i ≥ N.

Find the expected value of N.
Give your answer rounded to 10 digits after the decimal point.

---

随机整数按位或运算

记y₀、y₁、y₂、……是一系列32比特无符号随机整数。
（也就是说，0 ≤ y_i < 2³²，其中每个数等概率出现)。

序列x_i按如下方式递归定义：

• x₀ = 0，以及
• 对于所有 i > 0，x_i = x_i-1 | y_i-1。（|指按位或运算符）

可以看出，存在下标N，使得对于所有i ≥ N，x_i = 2³² -1（所有比特位均取1）。

求N的期望值。
将你的答案保留小数点后十位小数。

---