# Maximum number of distinct values for bitwise OR

You are given an array with $N$ elements. The values of the elements may be any number in the interval $[0,10^9]$. Define $f(a,b)$ as the bitwise or of all the values in the subarray $[a,b]$. Find a bound on the number of distinct values of $f(a,b)$.

Attempts: I have tried to brute force cases to find a pattern but was unsuccessful.

• This bound is actually tight for $N<30$, roughly. – Yuval Filmus Jun 13 '18 at 5:42
• Another simple bound is $2^{30}$, which is also tight. – Yuval Filmus Jun 13 '18 at 6:44