Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.


Two 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.


You 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...


Fortunately my encounters with C and C++ have been rare and brief.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: