Thread: Computing Trailing Zeros HOWTO

Hi everyone,

as mentioned in another post, there exists a nice trick to compute the number of trailing zeros in an int's binary representation in constant time, i.e. without using a loop.

In an attempt to get a grip on DocBook XML, I wrote an HOWTO on that topic, see http://www.0xe3.com/text/ntz/.

I hope that some of you can come up with comments, ideas and corrections, and apart from the actual content also about the proper use of the English language. I've never taken the opportunity to talk to an English native speaker, so I'm quite uncertain about syntax, grammar and semantics.

Either way, I'd be glad to hear from you.

Greets,
Philip

Well you're doing pretty good considering:

I've never taken the opportunity to talk to an English native speaker, so I'm quite uncertain about syntax, grammar and semantics.

Which is to say better than most native English speakers, of whom I know numbers.
I'll keep updating this post if I find any "errors". But I might not read it all right now.

One thing I'd observe is that when you first introduce the concept of de Bruijn sequences (2.1) with an example, and then say:

Have you already found some de Bruijn sequence of length 8?

You might want to complete the statement, ie. "of length 8=2^3?", since non-hardcore math types like myself might momentarily think they are always about the number three.

...this is great so far (3.1), you are really tripping me out

You lost me by the end, in the sense that I read it through a couple of times but could not quite get my head around what was going on. However, I doubt that's your fault, and I'm sure if I really had to understand, your explanation contains enough information (I didn't try any code, I'm happy with what I learned about binary representation in the first part). The style is genuinely nice and you don't have any syntax problems with English, "SNAFUist".

Looks like a good article to me. I believe I now know what a De Bruijn sequence is.

I was thinking that this algorithm should be included on the bithacks website, and it turns out that it is already:
http://www-graphics.stanford.edu/~se...ightMultLookup

It's good to come closer to fully understanding it now though.

You might want to complete the statement, ie. "of length 8=2^3?"

Good point, it's fixed now.

You lost me by the end

Yep, I think the transition from the background section to the algorithm itself is too abrupt. Of course, the reader is required to get his thoughts together at this point, but maybe I can come up with some charming words to at least present it in a comfortable atmosphere.

I was thinking that this algorithm should be included on the bithacks website

Excellent reading, haven't heard of it. I added a chapter "Further Readings" and included links to the website, appended the author's code in the section "Putting it all together" and informed him about my HOWTO.


Thanks for your suggestions, this was really helpful. I think I was able to apply some minor improvements here and there, but if there's anything left that comes to your mind, please let me know.

Greets,
Philip