4 ms·
Super cool, I'll have to have closer look sometime. To handle zero, if you have ctz, you can replace the divide with two bitwise shifts. This may sometimes be
by anonymoushn 4y ago
Super cool, I'll have to have closer look sometime. To handle zero, if you have ctz, you can replace the divide with two bitwise shifts. This may sometimes be faster than the divide even if you don't have ctz.
- danbruc 4y agoTwo shifts? I think ctz plus a single shift should do. shiftedOnes = (x & (rightmostZeroOneEdge - 1)) >> ctz(x) // This must be a logical shift. With all the fancy bit level instruction, this could probably be simplified in general, but I usually avoid them because I mostly see this as an exercise in making it work if you only have access to the basic arithmetic and logic operations and shifts.
- anonymoushn 4y agoYou need two shifts in C++ because shifting a uint32_t by 32 is UB. Every actual computer probably gives you 0 if you shift 0 right by a too-large amount though...
- danbruc 4y agoFortunately my encounters with C and C++ have been rare and brief.