4 ms·
Sure! The simplest is a loop that increments a counter if the least significant bit is 1 and right shifts the word by 1 each iteration. Bonus points for early
by pacaro 7y ago
Sure!
The simplest is a loop that increments a counter if the least significant bit is 1 and right shifts the word by 1 each iteration. Bonus points for early termination
One weird trick is to consider (w & (w - 1)) which unsets the lowest set bit
The other major approach is to use lookup tables for some segment of the word, usually nybble or byte, if this is done on a divide and conquer approach you can short-circuit parts of the word that are zero
[Edit] dalke's answer is much more detailed! I last thought about this stuff in about 2001 or so
- eru 7y agoBtw, depending on application, sometimes you don't want early termination. Eg for some cryptographic applications you don't want to leak information about what data you are working on in the runtime of your algorithm. Another (more far-fetched?) scenario might come up with either branch prediction and CPU pipelining, or your compiler's optimizer recognising the simple loop but not the one that has early abort.
- pacaro 7y agoYeah, creating constant time code is its own challenge, if a candidate were to bring that up it could take the interview down a very different path
- a1369209993 7y ago> either branch prediction and CPU pipelining Not that far-fetched; the non-early-aborting loop can be branch-predicted perfectly by a smart enough CPU.