What is this byte lookup table?

Question

I came across this byte lookup table and was trying to identify the pattern. What is it generated from?

There is a similar byte lookup here on SO but it starts with 0x00. How can I shuffle bits efficiently? Seems like a good way to do things like counting the number of bits that are flagged on in a large number for example.

   0x01 0x00 0x01 0x02 0x03 0x02 0x03 0x00 0x01 0x00 0x01 0x02 0x03 0x02 0x03 0x04
   0x05 0x04 0x05 0x06 0x07 0x06 0x07 0x04 0x05 0x04 0x05 0x06 0x07 0x06 0x07 0x00
   0x01 0x00 0x01 0x02 0x03 0x02 0x03 0x00 0x01 0x00 0x01 0x02 0x03 0x02 0x03 0x04
   0x05 0x04 0x05 0x06 0x07 0x06 0x07 0x04 0x05 0x04 0x05 0x06 0x07 0x06 0x07 0x08
   0x09 0x08 0x09 0x0a 0x0b 0x0a 0x0b 0x08 0x09 0x08 0x09 0x0a 0x0b 0x0a 0x0b 0x0c
   0x0d 0x0c 0x0d 0x0e 0x0f 0x0e 0x0f 0x0c 0x0d 0x0c 0x0d 0x0e 0x0f 0x0e 0x0f 0x08
   0x09 0x08 0x09 0x0a 0x0b 0x0a 0x0b 0x08 0x09 0x08 0x09 0x0a 0x0b 0x0a 0x0b 0x0c
   0x0d 0x0c 0x0d 0x0e 0x0f 0x0e 0x0f 0x0c 0x0d 0x0c 0x0d 0x0e 0x0f 0x0e 0x0f 0x00
   0x01 0x00 0x01 0x02 0x03 0x02 0x03 0x00 0x01 0x00 0x01 0x02 0x03 0x02 0x03 0x04
   0x05 0x04 0x05 0x06 0x07 0x06 0x07 0x04 0x05 0x04 0x05 0x06 0x07 0x06 0x07 0x00 
   0x01 0x00 0x01 0x02 0x03 0x02 0x03 0x00 0x01 0x00 0x01 0x02 0x03 0x02 0x03 0x04
   0x05 0x04 0x05 0x06 0x07 0x06 0x07 0x04 0x05 0x04 0x05 0x06 0x07 0x06 0x07 0x08
   0x09 0x08 0x09 0x0a 0x0b 0x0a 0x0b 0x08 0x09 0x08 0x09 0x0a 0x0b 0x0a 0x0b 0x0c
   0x0d 0x0c 0x0d 0x0e 0x0f 0x0e 0x0f 0x0c 0x0d 0x0c 0x0d 0x0e 0x0f 0x0e 0x0f 0x08
   0x09 0x08 0x09 0x0a 0x0b 0x0a 0x0b 0x08 0x09 0x08 0x09 0x0a 0x0b 0x0a 0x0b 0x0c
   0x0d 0x0c 0x0d 0x0e 0x0f 0x0e 0x0f 0x0c 0x0d 0x0c 0x0d 0x0e 0x0f 0x0e 0x0f 0x10
   0x11 0x10 0x11 0x12 0x13 0x12 0x13 0x10 0x11 0x10 0x11 0x12 0x13 0x12 0x13 0x14
   0x15 0x14 0x15 0x16 0x17 0x16 0x17 0x14 0x15 0x14 0x15 0x16 0x17 0x16 0x17 0x10
   0x11 0x10 0x11 0x12 0x13 0x12 0x13 0x10 0x11 0x10 0x11 0x12 0x13 0x12 0x13 0x14
   0x15 0x14 0x15 0x16 0x17 0x16 0x17 0x14 0x15 0x14 0x15 0x16 0x17 0x16 0x17 0x18
   0x19 0x18 0x19 0x1a 0x1b 0x1a 0x1b 0x18 0x19 0x18 0x19 0x1a 0x1b 0x1a 0x1b 0x1c
   0x1d 0x1c 0x1d 0x1e 0x1f 0x1e 0x1f 0x1c 0x1d 0x1c 0x1d 0x1e 0x1f 0x1e 0x1f 0x18
   0x19 0x18 0x19 0x1a 0x1b 0x1a 0x1b 0x18 0x19 0x18 0x19 0x1a 0x1b 0x1a 0x1b 0x1c
   0x1d 0x1c 0x1d 0x1e 0x1f 0x1e 0x1f 0x1c 0x1d 0x1c 0x1d 0x1e 0x1f 0x1e 0x1f 0x10
   0x11 0x10 0x11 0x12 0x13 0x12 0x13 0x10 0x11 0x10 0x11 0x12 0x13 0x12 0x13 0x14

Knowing this would really help in make the answer clear. – Ry- Jul 07 '17 at 06:58 — Ry-, Jul 07 '17 at 06:58

user2357112 · Accepted Answer · 2017-06-29T04:17:39.663

There's actually an Online Encyclopedia of Integer Sequences! Plugging your numbers into the OEIS search turns up A059905: Index of first half of decomposition of integers into pairs based on A000695, with a comment describing it as "One coordinate of a recursive non-self intersecting walk on the square lattice Z^2". OEIS gives several ways to compute the sequence.

There are plenty of other ways to characterize this sequence and other ways it might turn up, including the bit-shuffle application you linked. We can't tell what the intended use of the table was wherever you came across it just by seeing the values or knowing that it's OEIS A059905, but knowing the math behind it helps understand it better.

If you ever want to know what a mysterious sequence of integers might be, OEIS is a good resource to try.

Awesome resource, thank you! That at least gives the numbers some meanings. To actually generate these numbers, it looks like it has something to do with Moser-de Bruijn sequence: sums of distinct powers of 4 specifically n = A000695(a(n)) + 2*A000695(A059906(n)) where n is the index of this array. — user99999991, Jun 29 '17 at 23:20

What is this byte lookup table?

1 Answers1