Interleaving numbers

Posted 25 November 2010

When you have two numbers that need to be indexed together for speedy lookups there are a variety of mechanisms that can be used, a fast and efficient mechanism is called the Morton Interleave.

<?php
/**
* Calculate a Morton Interleave for two numbers.
*
* @param    int   \$x   The first number
* @param    int   \$y   The second number
* @return   int      The Morton Interleave
* @author   Aidan Lister <aidan@php.net>
*/
function interleave(\$x, \$y) {
\$result = 0;
\$position = 0;
\$bit = 1;

while (\$bit <= \$x || \$bit <= \$y) {
if (\$bit & \$x)
\$result |= 1 << (2*\$position+1);
if (\$bit & \$y)
\$result |= 1 << (2*\$position);

\$position += 1;
\$bit = 1 << \$position;
}
return \$result;
}

?>

A common use case for the interleave is storing a conversation between two users. For example, to retrieve all messages between user 231 and user 119 one would normally query the database with WHERE (sender_id=231 AND receiver_id=119) OR (sender_id=119 AND receiver_id=231).

When using an interleave field, you could do something like WHERE conversation_id=48447. The number 48447 being the interleave, calculated as:

<?php

\$uids = array(231, 119);
interleave(max(\$uids), min(\$uids));

?>

This means faster queries and cleaner code!