Computing Trailing Zeros HOWTO

This is a discussion on Computing Trailing Zeros HOWTO within the C Programming forums, part of the General Programming Boards category; Hi everyone, as mentioned in another post, there exists a nice trick to compute the number of trailing zeros in ...

  1. #1
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312

    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
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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
    Last edited by MK27; 02-21-2009 at 12:52 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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".
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    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
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Computing Degree Question
    By cjwenigma in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 09-17-2007, 01:06 PM
  2. small Distributed computing utilies
    By vinit in forum C Programming
    Replies: 2
    Last Post: 04-17-2006, 03:37 AM
  3. display double w/o trailing zeros?
    By Navar in forum C Programming
    Replies: 10
    Last Post: 02-11-2006, 02:27 PM
  4. why does printf output include a trailing 'D'
    By musikluvah in forum C Programming
    Replies: 5
    Last Post: 01-16-2006, 03:38 AM
  5. saving a CString to binary file with trailing spaces
    By nineofhearts in forum C++ Programming
    Replies: 12
    Last Post: 01-03-2006, 10:53 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21