3 ms·
Naturally, x86 has a useful opcode for this: BSR, bit-scan right. It tells you the index of the first set (1) bit scanning from most-significant to least-signif
by DarkShikari 15y ago
Naturally, x86 has a useful opcode for this: BSR, bit-scan right. It tells you the index of the first set (1) bit scanning from most-significant to least-significant. It returns the index from 0=LSB, 31=MSB.
BSR/BSF are the equivalents of CLZ/CTZ on ARM and other CPUs; it isn't a "crufty" or "redundant" instruction in the same way as LOOP, etc. Most modern x86 CPUs implement it in 1 or 2 cycles, with the exception of Athlon 64 and Atom. Check Agner's list of instruction latencies; don't guess.
BSF/BSR are extraordinarily useful instructions for a wide variety of uses, the most common being integer log2 (useful for parsing variable-length codes).
- adgar 15y agoI never said it was crufty, just that it wasn't successful for me in improving my use-case despite requiring noticeably fewer instructions (not cycles). I am, however, on Athlon 64. That may explain why I found it to be indistinguishable to the short loop in profiling. I didn't guess anything, I even explicitly explained my profiling methodology.
- arto 15y agoHere's a link to Agner's optimization manuals, for the benefit of those who may not be familiar with them: http://www.agner.org/optimize/#manuals http://www.agner.org/optimize/#manuals In short they contain what is probably the best x86 instruction latency reference, based on actual empirical measurements on various Intel/AMD/VIA chips.