Maximum value of $\{ i \land n \mid a \leq i \leq b \}$

Question

I was doing problems in "Leetcode" and found a problem that I could not solve.

Given a non-negative number $n$ and two non-negative numbers $a$ and $b$, consider every number $i$ such that $a \leq i \leq b$ and among those find the maximum value of $n \& i$ where $\&$ means bitwise and.

I could only solve when $a=0$ by finding the most significant bit location in $b$ and in $n$ and comparing both and find that $i$ should be $b$ or let location of most significant bit be $k$ from right then it must be $1111111.......1$ $(k-1)$ times.

But when $a \neq 0$ I am struck. Can anybody help me?

P.S : I am finding the question and I will post it's link by tomorrow.

Answer 1

Here is how to reduce this to the case you already know how to solve.

If $a = b$, there is nothing to do. Otherwise, the binary expansion of $a,b$ is of the form $a = x0\alpha$ and $b = x1\beta$, where $|\alpha| = |\beta|$. If the bit of $n$ corresponding to the differing bit of $a,b$ is $0$, then the corresponding bit of $i$ should be $1$, and vice versa (more significant bits are forced to $x$).

In the first case, we are looking for a solution in the range $x10^{|\beta|}$ to $b$, which reduces to $0^{|\beta|}$ to $b$; that you already know how to solve.

In the second case, we are looking for a solution in the range $x0\alpha$ to $x01^{\alpha}$, which reduces to $\alpha$ to $1^{|\alpha|}$; that should have a solution analogous to the case you're familiar with.