Morton encoding/decoding through bit interleaving, or how to interleave the bits of n-integers of m size. See also: * Morton Numbers * Morton Keys * Z-Order Curve Goal: efficient UB-Tree indexing

gistfile1.txt

http://en.wikipedia.org/wiki/Z-order_curve
http://stackoverflow.com/questions/18529057/produce-interleaving-bit-patterns-morton-keys-for-32-bit-64-bit-and-128bit
http://stackoverflow.com/questions/1024754/how-to-compute-a-3d-morton-number-interleave-the-bits-of-3-ints
http://code.activestate.com/recipes/577558-interleave-bits-aka-morton-ize-aka-z-order-curve/
http://www.forceflow.be/2013/10/07/morton-encodingdecoding-through-bit-interleaving-implementations/
https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/part-1
https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/part-2


It turns out we don't have to actually interleave the bits if all we want is the ability to compare two keys as if they had been interleaved. What we need to know is where the most significant difference between them occurs. Given two halves of a key we can exclusive or them together to find the positions at which they differ.