RE: [Algorithms] Bit fiddling
Brought to you by:
vexxed72
From: John M. <jmc...@re...> - 2002-02-04 13:01:51
|
Tom Forsyth writes: >I suspect the other version may be more efficient, and obviously far more >portable, but hey - I got rid of the loop :-) You've unrolled the loop, that's all (and in a most unusual way - it must be nice to have a decent sized instruction cache and not have to worry about code size :-) For high values of consecutiveBitCount it will still execute a lot of shifts and ands. It should be possible to reduce the loop, by re-using earlier parts of the calculation, but I don't have the time right now to develop it properly. b2 = value & value>>1 b4 = b2 & b2>>2 b8 = b4 & b4>>4 b16 = b8 & b8>>8 If consecutiveBitCount is a power of 2, then one of the b values should be what you want (if I'm not deranged). If it isn't, then you'll need to throw in some other terms. Does that work? So far, there have been two parts to the algorithm: first find a bit that is in the lowest position of the consecutive run, and then find its position in the word. If it exists, a find-first-one instruction will perform the second task much faster than anything else I can imagine. -Virus scanned and cleared ok |