Circuit to find difference, in binary, between most significant and least significant 1

Question

If A = 1100, and B = 1010, I want to find the positional difference between the first 1 from the left on A, and first 1 from the right on B. In this case the answer would be 10.

In other words, the circuit would find how many times i need to shift B to left, to allign its rightmost 1 to A's leftmost 1.

How could such a circuit be created? Preferably in the best O time?

I could do it with a logic table, but that seems rather tideous for a 32 bit circuit. My example was just 4 bit for simplicity. I am implementing this in logism - a digital logic simulator.

Answer 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.