0

How do you generate this table used in this "count trailing zeroes" algorithm?

/* Using a de Bruijn sequence. This is a table lookup with a 32-entry
table. The de Bruijn sequence used here is
                0000 0100 1101 0111 0110 0101 0001 1111,
obtained from Danny Dube's October 3, 1997, posting in
comp.compression.research. Thanks to Norbert Juffa for this reference. */

int ntz10(unsigned x) {

  static char table[32] =
    { 0, 1, 2,24, 3,19, 6,25,  22, 4,20,10,16, 7,12,26,
      31,23,18, 5,21, 9,15,11,  30,17, 8,14,29,13,28,27};

  if (x == 0) return 32;
  x = (x & -x)*0x04D7651F;
  return table[x >> 27];
}

Looking into de Bruijn graphs to see if that might help. Perhaps this is useful as well.

Lance
  • 75,200
  • 93
  • 289
  • 503
  • How about simply computing `(x*0x04D7651F & 0xFFFFFFFF) >> 27` for each power of 2 `x` between `1` and `2^31`, and then rearranging the results accordingly. In Python, the following one-liner gives me a table that exact matches yours: `d = {(1<> 27 & 0x1F: i for i in range(32)}; [d[i] for i in range(32)]` – Mark Dickinson Apr 20 '22 at 12:19
  • 2
    Note that your code isn't strictly portable: it assumes that `int` has width exactly 32. I'd recommend (a) using `uint32_t` from `stdint.h`, and (b) using `(x & 0xFFFFFFFF) >> 27` instead of `x >> 27` in the table lookup. (On most machines, that mask will be a no-op, but if your code does someday meet a machine with 64-bit ints, it'll continue to work.) – Mark Dickinson Apr 20 '22 at 12:23
  • @MarkDickinson how do you mean? I don't know how this magic works. I figured out [how to generate de Bruijn sequences from a graph](https://stackoverflow.com/a/71957347/169992), yay! But what do I do to generate this table (or other similar tables)? [This](https://stackoverflow.com/questions/7365562/de-bruijn-like-sequence-for-2n-1-how-is-it-constructed) is the only thing that is somewhat helpful so far. – Lance Apr 21 '22 at 17:53
  • You know that if `x = 1 << i` then `ntz10(x)` must give a result of `i`. That fact tells you exactly _where_ the number `i` must go in `table` in order to make the lookup work - specifically, the value at index `(1<> 27 & 0x1F` of the table must be `i`. Iterating over all `i` in the range `0 <= i < 32` then fills out the table. Did you try the Python code I gave you? (You can just copy and paste it at a Python prompt.) It does exactly this. – Mark Dickinson Apr 21 '22 at 18:31
  • As an example, `(1 << 5) * 0x04D7651F >> 27 & 0x1F` gives `19`. That tells you that the table entry at position `19` must be `5`. Similarly, `(1 << 24) * 0x04D7651F >> 27 & 0x1F` gives `3`, so the entry at index `3` must be `24`. – Mark Dickinson Apr 21 '22 at 18:39

0 Answers0