Bitwise-OR Operations on Random Integers

Let $y_0, y_1, y_2, \dots$ be a sequence of random unsigned $32$-bit integers
(i.e. $0 \le y_i \lt 2^{32}$, every value equally likely).
For the sequence $x_i$ the following recursion is given:$x_0 = 0$ and
$x_i = x_{i – 1} \boldsymbol \mid y_{i – 1}$, for $i \gt 0$. ($\boldsymbol \mid$ is the bitwise-OR operator).
It can be seen that eventually there will be an index $N$ such that $x_i = 2^{32} – 1$ (a bit-pattern of all ones) for all $i \ge N$.
Find the expected value of $N$.
Give your answer rounded to $10$ digits after the decimal point.

This is a problem that involves understanding of bitwise operations and probabilistic analysis.

Bitwise-OR operation takes two bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bit. For example, if n1 = 12 (represented as 1100 in binary) and n2 = 25 (represented as 11001 in binary), then bitwise OR operation for n1 and n2 can be performed as follows:

n1 = 1100 (in binary)
n2 = 11001 (in binary)

n1|n2 = 11101 (in binary)

Thus n1|n2 = 29 (in decimal)

In the recursive relation $x_i = x_{i – 1} \boldsymbol \mid y_{i – 1}$ for $i \gt 0$, the variable $x_i$ will get more and more bits set to 1 after each step, due to the bitwise OR operation. Given 32 bits, once all bits are set to 1, then the number will be $2^{32} – 1$, and hence no matter what $y_i$ is, $x_i$ will remain as $2^{32} – 1$.

Every step we perform bitwise OR with a new random 32 bit number $y_i$. This can be viewed as flipping a coin for each bit in $x_i$, if it is not set yet (probability $p = 0.5$). If we happen to flip a 1, then this bit will remain 1 forever. As we have 32 bits, we are looking for expected number of flips N to turn all bits to 1 which equals to $N = 32/p$ (a well known result in probability theory).

Hence,
$N = 32/0.5 = 64$.

This result is to be interpreted as that we expect to flip 64 independent random 32-bit numbers on average before all the bits in $x_i$ are set to 1.

So, the answer, without rounding, would be $N = 64.0000000000$.

More Answers: