Hi all, I've a tricky little question for you.

A friend of mine is trying to do some optimisation, and he has one operation that he does again and again. If he could speed it up, it'd help no end.

He is storing a number of the form 2^a as an integer, and he wants to get the a as quickly as possible. So, in binary, he might have:
2^3 (0000000000001000)
so he wants the integer 3 from that. He's happy to consider a hardware solution or anything.

What he's doing right now, AFAIK, is a check on each half (not sure of the detail), iterated until he's down to one location. Is there anything faster?

Some time ago, a link to this very neat page was posted in a thread on the forums. I suggest you try the "// OR (IF YOU KNOW v IS A POWER OF 2)" example. I think I figured out how it works

Best regards,
Lucian

__________________
Please read these Guidelines before posting on the forum

"A person who never made a mistake never tried anything new."
Einstein

Thanks, but that's the complexity (O(log(n))) he has already. I suspect that there isn't a faster way TBH.

If you have a 32-bit one-hot number and you want to know the position of the 1, then the output will be a number greater than or equal to zero and less than or equal to 31 (a five-bit number). I assume here that a 1 in the least significant position will yield a value of zero, and a 1 in the most signficant position will yield a value of 31 decimal (0x1f hex).

Your friend is probably determining each bit independently. This can be done (easily) if you allow each bit decision to consist of a single logical operation and comparison. Since there are five bits in the result, there will be five decisions. (Is this what you mean by (O(log(n))? SInce log of 32 to the base 2 is five, this may be the ultimate for this kind of problem). Since it's easy to do 32-bit operations with built-in operators and data types, a C program is kind of trivial (and short). See footnote.

An equivalent combinatorial hardware impelementation could consist of five 32-input and gates; logic inverters may be necessary for each of the 32 input bits, depending on the exact nature of the gates. Conceptually simple, and easy to do in an FPGA or PLD, but low-cost devices usually don't have enough pins (32 inputs, 5 outputs, power, ground).

Hardware and software solutions may require a bit more logic to implement some kind of "data valid" output that is desirable in general just in case it is presented with an invalid input--- That is: no bits set or more than one bit set in the input word. (A little pun, get it? A "bit" more logic? No? Oh, well...)

There are more complex structures that consider more than one bit at a time

For example, consider a Read-Only Memory that has 32 address bits and five data output bits. Consider that you have defined the ROM contents so that the data value for address 0x00000001 is 0, the data value for 0x00000002 is 1, the data value for address 0x00000004 is 3, ..., the data value for adress 0x80000000 is 32 decimal (0x1f hex). And all other locations are zero.

Of course this requires a 4 gigaword 5-bit memory to hold the 32 relevant outputs. Probably not practical unless speed is the only consideration (and price is no object). It can be done combinatorially and the propagation delay is dependent on the technology. Custom large ROMs for such a simple application seems like a large amount of overkill, but, hey, it's your money.

Then, there are Content-Addressable Memory elements (CAMs) that are used in network routers and other places where you store a "key" value at a given address, then you can do a "reverse lookup" by giving the key value and the CAM will give you the address.

So you store key value 0x00000001 in address 1
store key value 0x00000002 in address 2
store key value 0x00000004 in address 3
.
.
.
store key value0x80000000 in address 32

You only need 32 entries in the CAM, compared with over 4 billion for the ROM.


Now if you apply a value of 0x02000000, the CAM gives you 25. (Indicating that bit number 25 is set).

Error detection is automatic, since any illegal input will not have had a key value stored, and the CAM will give a "no joy" output.

You may be able to find a commercial device, or you may be able to design a FPGA or PLD to implement it in hardware.

Again, there may be quite a bit of logic in the design, but it can give you your result in a single clock cycle (they are usually implemented in a way that requires a clock, and clock speed depends on the technology, obviously). Still pretty pricey for a simple application like this, but, a possibility if price is no object.

Regards,

Dave

Footnote: For the following example, I could have put all of the bit operations into a single C statement, but I separated them for purposes of illustration. If you don't see how it works, then print out the results at each step. Note that since speed is supposedly important, I didn't try to do something elegant like making a loop with a cleverly designed way of creating a bit mask or any such thing. Of course for maximum speed, I would have made it an in-line function (or, even, a macro) with a single statement.

Left As An Exercise For The Interested Reader: How would you put in error detection? What would be the impact on program size and run time? Would you still be able to implement it with a macro or an in-line function, given that it has two return values? (Or could you just define an extra output bit that holds the "valid" condition?)

I know that GNU gcc has the C99 Standard defined <inttypes.h> that I use to make sure the input will be a 32-bit number. Most compilers these days have 32-bit ints (and they don't seem to have <inttypes.h>), so I put in a test to make sure --- at least it works for me with Borland and Microsoft compilers to which I have access. Of course, for a given compiler, once you have verified the size of whatever data type you have, you can leave out the assertion stuff, but I kind of like having it there just in case I absent-mindedly try to port stuff like this to development environments with limited capabilities (besides creaky old Borland TurboC, lots of compilers for small microcontrollers have 16-bit ints).


Output

Wow, thanks Dave. The CAM solution looks interesting.

Yeah, by O(log(n)) I meant 5 clock cycles here.