Number of distinct numbers that can be obtained

Question

I am looking for the number of distinct numbers that can be obtained by OR operation on any subset of $\{L, L+1, L+2,...,R\}$.
Note that we OR operation on a subset of size $1$ is the element itself.

Answer 1

Let $r$ be the 1st bit where $A,B$ differ. So we can remove the bits before this from both $A,B$ as they won't affect our answer because no matter what nos we select in OR operation those bits will remain as it is, and thus have just 1 choice.
Now, $A<2^r\le B <2^{r+1}$
This equation is really very important as we will see later on.
Let $T=2^r$, and lets partition the nos from $A$ to $B$ into 2 sets:
$X=\{A,A+1,...,T-1\}$ and $Y=\{T,T+1,...,B\}$
1. Taking nos from only X:
We can obtain all nos from $A$ to $T-1$. That's it. We can't obtain higher nos as $T-1$ is already a bit sequence of all ones.
2. Taking nos from only Y:
This is interesting.
Note that $T\le B <2^{r+1}$, so $T,B$ have same number of bits.
The highest bit set in both $T,B$ is $r$. Infact $T$ has only one bit set.
Let the next highest bit set in $B$ be $k$.
Now refer to the pic below.
We can trivially obtain all nos from $T$ to $B$. Point is how far can we go from $B$. Now refer to the image above and read the following. The nos between $2^r$ and $2^r+2^k$ will be of form $1000*****$. The shaded portion of length $k-1$ bits will have all permutations of $0$s and $1$s(from $0$ to $2^k-1$). So we can set any pattern of $0$s and $1$s in the first $k-1$ bits of $B$ by suitable OR operations. This enables us to obtain any number from $B$ to $2^r+2^{k+1}-1$. Voila!

So in this case, we can obtain nos from $T$ to $2^r + 2^{k+1}-1$.

3. Taking nos from X and Y: The min number thus obtained will be the OR of $A,T$ = $A+T=A+2^r$. Note that $T$ just has a bit set at $r^{th}$ position, while all nos from $X$ have bits from $0$ to $r-1$. $\therefore$, OR of $T=2^r$ with elements from $X$ will give us nos from $A+T$ to $T-1+T=2T-1$. Well, this is the highest number that we can achieve as it is $2^{r+1}-1$ i.e all bits set to $1$. So we can't go any further.

Finally we have 3 segments, some of which may overlap. All that is left is to find the total length spanned by these segments. Phew!

Answer 2

There is an easy upper bound. Let $n$ be the minimum value such that $2^n-1 \ge R$. You can't get anything below $L$ or anything above $2^n-1$, so there would be at most $2^n-L$ values available. This can be too large. If we take $L=12,R=17$ we would think we might get $32-12=20$ different numbers but we can never have the fours bit and eights bit different so we can only get $12-19,28-31$ for $12$. The last seems easy to see but hard to express properly.