6 ms·
Computing Trailing Zeros (2009)
- nemo1618 8y agoPretty neat. You can see this exact approach in the Go standard library: https://golang.org/src/math/bits/bits.go#L35 https://golang.org/src/math/bits/bits.go#L35 Nowadays, of course, ctz gets compiled down to a single instruction (e.g. bsf on x86) :)
- FabHK 8y agoAnyone got a cache? I can't access it. The title reminded me of this Project Euler problem named "Factorial trailing digits": https://projecteuler.net/problem=160 https://projecteuler.net/problem=160
- bsder 8y agoMore Bit Twiddling Hacks: https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html
- kccqzy 8y agoI was once asked this exact question in a technical interview. I used __builtin_ctzll and that dumbfounded the interviewer. (Disclaimer: this may or may not be a good thing to do in an interview depending on the role/interviewer.) In the real world, you probably want to use this builtin or something provided by the compiler/standard library as opposed to rolling your own.
- pmiller2 8y agoMirror: http://web.archive.org/web/20190410000033/http://7ooo.mooo.com/text/ComputingTrailingZerosHOWTO.html http://web.archive.org/web/20190410000033/http://7ooo.mooo.c...
- tromp 8y agoWhile the papers mentions odd numbers as a possible special case in a sidenote, the real special case is x=0. The given expression size_t i = ((x & -x) * debruijn) >> 27; treats x=0 the same as odd x, since 0debruijn>>27 == 1debruijn>>27 == 0.