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

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.

• It's O(1) time if you do it with a look-up table (ROM). Is that the answer you're looking for? Jan 10, 2020 at 4:21
• Are you implementing this with discrete logic? In an FPGA? In an ASIC? Jan 10, 2020 at 4:22
• Sound like you are going to perform 32-bit division, and trying to optimize ahead. If it is the case, then your "optimized" solution may cause more footprint and be less predictable in speed. Did you already implement head-on algorithm with 63-bit input register and 63 clock cycles, and fixed predictable result latency? Jan 10, 2020 at 7:32
• The logic to find the leftmost or rightmost "1" in a word is called a "priority encoder". You need one for A with the highest priority on the left, and one for B with the highest priority on the right. Jan 10, 2020 at 12:05

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.