# Forum: FPGA, VHDL & Verilog Puzzle- Position of Most Signi '1' in an N-bit register

 Author: Antony Mathew (antony_mat) Posted on: 2015-07-14 14:57

Rate this post
 0 ▲ useful ▼ not useful
Seems simple, but i am done with this question... May be smart guys here

I have an N bit Register with any one of the possible 2^N values.
Need to retrieve the position of Most Significant '1' in the register.

eg:-
Consider a 4 bit register reg <= '0101' . Output should be 2.

OR once again

reg <= '1101' . Output should be 3.

Need a hardware algorithm for this...
Cracks my head....

: Edited by User
 Author: Klaus (Guest) Posted on: 2015-07-14 15:08

Rate this post
 0 ▲ useful ▼ not useful
There is no such thing like an 'hardware algorithm'. I think you meant
an: 'algorithm, realized in hardware'.

What about porting a software solution into an hardware? There are
plenty of results for the search term "most significant bit set".
Probably some in pure hardware too.

A very famous hit, I assume one of the most often cited results, is:
http://graphics.stanford.edu/~seander/bithacks.html

 Author: Antony Mathew (antony_mat) Posted on: 2015-07-14 15:20

Rate this post
 0 ▲ useful ▼ not useful
There is no such thing like an 'hardware algorithm'. I think you meant
an: algorithm, realized in hardware'.

yep Klaus... thank you for the correction of context.

'algorithm, realized in hardware' seems the correct way of expressing
it.

 Author: Klaus (Guest) Posted on: 2015-07-14 15:28

Rate this post
 0 ▲ useful ▼ not useful
Was a pleasure. :-)

If you need help for transforming an algorithm expressed in an
imperative language to a hardware description, feel free to ask here any
further question, provided it is 'specific'.

hardware structure of a common cpu. This would lead to a merely
over-engineered design, but is a good start for optimization.

But another solution came to my mind: What about the most simple
solution? A look-up-table? Not realy educiational but easy. You question
may be read like asking for a generic solution. So a look-up-table may
be inefficient for greater bit counts, though.

 Author: Klaus (Guest) Posted on: 2015-07-14 15:32

Rate this post
 0 ▲ useful ▼ not useful
And I need help with English. :-)

Should be: "If you need help with transforming ..."

 Author: VHDL hotline (Guest) Posted on: 2015-07-14 16:18

Rate this post
 0 ▲ useful ▼ not useful
How much time do you have? N cycles? Make a shift register and a
counter.

 Author: antony mathew (Guest) Posted on: 2015-07-14 16:37

Rate this post
 0 ▲ useful ▼ not useful
No constraint on numb of cycles... method is the only concern. I tried
with an up/down counter with shifter... But was no success... Can u
elaborate on that ' VHDL hotline '

 Author: helpend (Guest) Posted on: 2015-07-14 18:00

Rate this post
 0 ▲ useful ▼ not useful
antony mathew wrote:
> No constraint on numb of cycles... method is the only concern. I tried
> with an up/down counter with shifter... But was no success... Can u
> elaborate on that ' VHDL hotline '

"No constain on number of cycles"...where is the problem then? Just copy
the register to a temporary one and shift left until the leftmost bit is
1. Count the amount of necessary shifts.

 Author: Lothar Miller (lkmiller) (Moderator) Posted on: 2015-07-14 20:28

Rate this post
 0 ▲ useful ▼ not useful
Try that:
http://www.lothar-miller.de/s9y/archives/55-Finde-...
You will see several solutions for that problem...

• $formula (LaTeX syntax)$