Moser–de Bruijn Sequence lookup and inverse lookup.

README.md

Moser–de Bruijn Sequence

According to Wikipedia, it consisting of the sums of distinct powers of 4.

The pattern is look like this: 0, 1, 4, 5, 16, 17, 20, 21, 64, ...

And the part of lookup table is look like this:

y-x	0	1	2	3	4	5	6	7	8
0	0	1	4	5	16	17	20	21	64
1	2	3	6	7	18	19	22	23	..
2	8	9	12	13	24	25	28	29	..
3	10	11	14	15	26	27	30	31	..
4	32	33	36	37	48	49	52	53	..
5	34	35	38	39	50	51	54	55	..
6	40	41	44	45	56	57	60	61	..
7	42	43	46	47	58	59	62	63	..

The pattern does exists at the y = 0 of the lookup table, and you may notice numbers of the table is increment by 1 in zig-zag shape.

How does the code work?

The algorithm is quite simple. First, if we make the table above in binary form, it will look like this:

y-x	00000	00001	00010	00011	00100	00101	00110	00111	01000
00000	00000	00001	00100	00101	10000	10001	10100	10101	...
00001	00010	00011	00110	00111	10010	10011	10110	10111	...
00010	01000	01001	01100	01101	11000	11001	11100	11101	...
00011	01010	01011	01110	01111	11010	11011	11110	11111	...

You may notice the relationship between the values and the axis value. For x-axis, 00001 will be 00001, 00010 will be 00100, and 00100 will be 10000, it maps its bits to odd bits; and for y-axis, 00001 will be 00010, and 00010 will be 01000, it maps its bits to even bits; and for the rest of the values, they are just mixing the mapped bits together. Therefore we have a conclusion here: If we label the bits for x-axis as 76543210, and y-axis as FEDCBA98, we should get the result value at specific cell like this: F7E6D5C4B3A29180, which is a simple binary shifting.

So for implementing the lookup function (or inverse lookup function), you will have to do is just make a bunch of bit mask, shift and union.

moser-de-bruijn-sequence.js

/**
 * JavaScript implementation for Moser–de Bruijn Sequence lookup and inverse lookup
 * More info:
 * Wikipedia: https://en.wikipedia.org/wiki/Moser%E2%80%93de_Bruijn_sequence
 * OEIS: https://oeis.org/A000695
 * 
 * The MIT License (MIT)
 * 
 * Copyright (c) 2017 Jeremy Lam (JLChnToZ).
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
;(function(root, factory) {
  if(typeof define === 'function' && define.amd)
    define(factory);
  else if(typeof exports === 'object')
    module.exports = factory();
  else
    root.MoserDeBruijn = factory();
}(this, function() {
  'use strict';
  var maxInt = Number.MAX_SAFE_INTEGER;
  return {
    // Lookup function for Moser–de Bruijn Sequence
    lookup: function mdbLookup(x, y) {
      if(!(x >= 0 && y >= 0))
        return 0;
      x = ~~x;
      y = ~~y;
      var r = 0;
      for(var m = 1, o = 0; (x >= m || y >= m) && m < maxInt; m <<= 1)
        r |= (x & m) << o++ | (y & m) << o;
      return r;
    },
    // Inverse lookup function for Moser–de Bruijn Sequence
    getPosition: function getMdbPosition(v) {
      if(!(v >= 0))
        return [0, 0];
      v = ~~v;
      var x = 0, y = 0;
      for(var m = 1, o = 0; v >= 1 << o + 1 && m < maxInt; m <<= 1) {
        x |= v >> o++ & m;
        y |= v >> o & m;
      }
      return [x, y];
    }
  };
}));

MoserDeBruijn.cs

public static class MoserDeBruijn {
    private const int MaxValue = int.MaxValue;

    public static int Lookup(int x, int y) {
        if(x < 0 || y < 0) return 0;
        int result = 0;
        for(int mask = 1, offset = 0; (x >= mask || y >= mask) && mask < MaxValue; mask <<= 1)
            result |= (x & mask) << offset++ | (y & mask) << offset;
        return result;
    }

    public static bool InverseLookup(int value, out int x, out int y) {
        x = 0;
        y = 0;
        if(value <= 0) return false;
        for(int mask = 1, offset = 0; value >= 1 << offset + 1 && mask < MaxValue; mask <<= 1) {
            x |= value >> offset++ & mask;
            y |= value >> offset & mask;
        }
        return true;
    }
}