0
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ It's O(1) time if you do it with a look-up table (ROM). Is that the answer you're looking for? \$\endgroup\$
    – The Photon
    Commented Jan 10, 2020 at 4:21
  • \$\begingroup\$ Are you implementing this with discrete logic? In an FPGA? In an ASIC? \$\endgroup\$
    – The Photon
    Commented Jan 10, 2020 at 4:22
  • \$\begingroup\$ 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? \$\endgroup\$
    – Anonymous
    Commented Jan 10, 2020 at 7:32
  • \$\begingroup\$ 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. \$\endgroup\$
    – Dave Tweed
    Commented Jan 10, 2020 at 12:05

1 Answer 1

0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.