Circuit to find difference, in binary, between most significant and least significant 1
How could such a circuit be created? Preferably in the best O time?


You can implement arbitrary logic by using the inputs as address inputs to a ROM, and putting the correct output values in the ROM memory. This is \$O(1)\$ in time. But of course this is \$O(2^n)\$ in space, so it is not always a good practical solution. For your problem with 4-bit inputs it would be a reasonable approach.

You could also use look-up tables to find the leftmost 1 position of A and rightmost 1 position of B, and subtract to get your result. The time complexity of this is whatever the time complexity of an adder is in your technology.

Any further optimization would likely trade off time for space, so finding the optimum for your actual application is down to details you haven't shared (and which are often only nebulously known in real-world projects) so it's your engineering judgement that will determine the best solution.