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.

Written by gamwe6 who lives and works in San Francisco building useful things. You should follow him on Twitter