For an integer \(i\), let \(P(i)\) denote the remainder when the number of bits that are set is divided by \(2\).
Bit positions are \(0\)-indexed.

When \(L\) is even or \(R\) is odd

Since we cannot include both \(2n\) and \(2n+1\) in \(S\), we have \(|S| \leq \lceil \frac{R-L+1}{2} \rceil\). Let \(E\) and \(O\) be the sets of integers \(i\) with \(L \leq i \leq R\) where \(P(i)\) is \(0\) and \(1\), respectively. Each of these satisfies the conditions. Since \(|E|+|O|=R-L+1\), we have \(\max(|E|,|O|) \geq \lceil \frac{R-L+1}{2} \rceil\), so the maximum value of \(|S|\) is \(\lceil \frac{R-L+1}{2} \rceil\), and the one with more elements between \(E\) and \(O\) is what we seek.

When \(L\) is odd and \(R\) is even

Reasoning similarly to above, we find that \(\frac{R-L+1}{2} \leq |S| \leq \frac{R-L+1}{2}+1\). If we can construct \(S\) with \(|S|=\frac{R-L+1}{2}+1\), that is what we seek; otherwise, \(E\) or \(O\) is what we seek.

When \(P(L)=P(R)\), we have \(\max(|E|,|O|)=\frac{R-L+1}{2}+1\), so the one with more elements between \(E\) and \(O\) is what we seek.

Consider when \(P(L) \neq P(R)\). Let the \(k\)-th bit be the most significant bit where \(L\) and \(R\) differ.

Consider when \(R<L+2^k\). Among integers \(i\) with \(L \leq i \leq R\), let \(S\) be the set satisfying either of the following:

• The \(k\)-th bit of \(i\) is not set, and \(P(L)=P(i)\)
• The \(k\)-th bit of \(i\) is set, and \(P(R)=P(i)\)

Then, \(S\) satisfies the conditions and \(|S| = \frac{R-L+1}{2}+1\), so this is what we seek.

When \(L+2^k \leq R\), we show that \(|S| \leq \frac{R-L+1}{2}\).
Prepare vertices corresponding to integers between \(L\) and \(R\), and connect edges between pairs of vertices where the number of differing bits is \(1\). It suffices to show that this graph has a perfect matching (this follows from the fact that we can only choose one from each matched pair. Alternatively, consider the relationship between maximum independent set and maximum matching in bipartite graphs).
First, match \((L+1,L+2),(L+3,L+4),\dots,(R-2,R-1)\). If we can find a path from \(L\) to \(R\) passing through some matched pairs, we can shift the matching along that path. Let \(k_1,k_2,\dots,k_C\) be the bit positions lower than the \(k\)-th bit where \(L\) and \(R\) differ, arranged in descending order. Starting from \(L\), for \(c=1,2,\dots,C\) in order, when we are at vertex \(X\), choose the pair \((X⊕2^{k_c},X⊕2^{k_c}⊕1)\) and move to vertex \(X⊕2^{k_c}⊕1\). From \(L+2^k \leq R\), the \(k_1\)-th bit of \(L\) is not set, the \(k_1\)-th bit of \(R\) is set, and the vertices we move to are always between \(L\) and \(R\). From \(P(L) \neq P(R)\), we end up at vertex \(R⊕2^k\) after moving, which is a vertex connected to \(R\), so we have shown that a perfect matching exists.