Find number between $A$ and $B$ with maximum set bits?

Question

Given two integers $A,B$. Find number $N$ which has maximum number of set bits in its binary form and lies between $A$ and $B$ inclusive. Is there any approach for this question. Also if there are multiple possible answers I want $N$ to be smallest of those.

Answer 1

Some hints:

Suppose the upper $k$ bits of $A,B$ match. Then for any $x$ satisfying $A \le x \le B$, the upper $k$ bits of $x$ will match those of $A,B$. You can do nothing about those except count them.

So, suppose the top bit of $A$ is 0 and the corresponding bit of $B$ is 1 (and both have $n$ bits). Then you should find a number in the range $A,...,B$ such that $N \ge n-1$.

There is only one possibility remaining after that.