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

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.

• Where is the link to the original problem? Apparently, this is not a problem on Leetcode. May 5 '20 at 2:08

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.

• But i did not understand your binary expansion ,and what is menaing of $x$ and ,why $|\alpha|=|\beta|$ ? May 4 '20 at 16:19
• Perhaps an example will help. Let $a=9$ and $b=12$. Then the binary expansion of $a$ is $1001$, and that of $b$ is $1010$. In this case $x = 10$, $\alpha = 1$, $\beta = 0$. May 4 '20 at 16:36
• It in answer it was mentioned that $|\alpha|=|\beta|$ May 4 '20 at 16:39
• Right: $|\alpha| = |\beta| = 1$. It's the length of $\alpha,\beta$ as bitstrings. May 4 '20 at 16:40
• And also meaning of $x10^{|\beta|}$ , May 4 '20 at 16:44