StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is sort of like finding a kind of integer log. There are bit-twiddling tricks, but I've made my own tool for this. The goal of course is for speed. </p> <p>My realization is that the CPU has an automatic bit-detector already, used for integer to float conversion! So use that.</p> <pre><code>double ff=(double)(v|1); return ((*(1+(uint32_t *)&ff))>>20)-1023; // assumes x86 endianness </code></pre> <p>This version casts the value to a double, then reads off the exponent, which tells you where the bit was. The fancy shift and subtract is to extract the proper parts from the IEEE value.</p> <p>It's slightly faster to use floats, but a float can only give you the first 24 bit positions because of its smaller precision.</p> <hr> <p>To do this safely, without undefined behaviour in C++ or C, use <code>memcpy</code> instead of pointer casting for type-punning. Compilers know how to inline it efficiently.</p> <pre><code>// static_assert(sizeof(double) == 2 * sizeof(uint32_t), "double isn't 8-byte IEEE binary64"); // and also static_assert something about FLT_ENDIAN? double ff=(double)(v|1); uint32_t tmp; memcpy(&tmp, ((const char*)&ff)+sizeof(uint32_t), sizeof(uint32_t)); return (tmp>>20)-1023; </code></pre> <p>Or in C99 and later, use a <code>union {double d; uint32_t u[2];};</code>. But note that in C++, union type punning is only supported on some compilers as an extension, not in ISO C++.</p> <hr> <p>This will usually be slower than a platform-specific intrinsic for a leading-zeros counting instruction, but portable ISO C has no such function. Some CPUs also lack a leading-zero counting instruction, but some of those can efficiently convert integers to <code>double</code>. Type-punning an FP bit pattern back to integer can be slow, though (e.g. on PowerPC it requires a store/reload and usually causes a load-hit-store stall).</p> <p>This algorithm could potentially be useful for SIMD implementations, because fewer CPUs have SIMD <code>lzcnt</code>. x86 only got such an instruction <a href="https://github.com/HJLebbink/asm-dude/wiki/VPLZCNTD_Q" rel="nofollow noreferrer">with AVX512CD</a></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload