Tim Blechmann wrote:

i see, maybe it would be an interesting addition to boost.integer to provide a generic and efficient version, based on bsr/ffs or the like ...

There is a lot of branchless or SWAR algorithm to salvaged from there and to be indeed made generic or at least platform independant w/r to various things. Other thign we never did is benching all of the versions of a given algorithm (with/without branch) on different platform to add a proper #ifdef/else to maximize performance.

there is a GSOC project "Bits and Ints" that is working on a lot off this kind of branch less algorithms. I can suggest him to include the integer runtime variant of some math functions, as log2.

that would be nice ... it would be even nicer, if you could suggest to make use of hardware instructions ... i am currently using this gcc-centric code [1] ... tim [1] http://tim.klingt.org/git?p=boost_heap.git;a=blob;f=boost/heap/detail/ilog2.... -- tim@klingt.org http://tim.klingt.org After one look at this planet any visitor from outer space would say "I want to see the manager." William S. Burroughs

What is "NT²" I've used an inline asm instruction for that. On the x86, there is a "Bit Scan Reverse" (BSR) which stores the index of the most-significant set bit.

-----Original Message----- In the good'ol Bits Twiddling Hacks page:

unsigned int v; // 32-bit value to find the log2 of unsigned int r; // result of log2(v) will go here unsigned int shift;

r = (v > 0xFFFF) << 4; v >>= r; shift = (v > 0xFF ) << 3; v >>= shift; r |= shift; shift = (v > 0xF ) << 2; v >>= shift; r |= shift; shift = (v > 0x3 ) << 1; v >>= shift; r |= shift;

TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.

ajb@spamcop.net wrote:

Many modern ISAs (at least EM64T, PPC and recent ARMs; these are just the ones I know about) have a single-instruction priority encoder usually called "count leading zeroes". In GCC, it's available as a builtin:

uint64_t log2v = v == 1 ? 0 : 64 - __builtin_clzll(v - 1);

Guess my old signal processing habits showed up ;) Of course, mapping to intrinsic is better I think. But I guess when they are not there, we need a fallback ;)