Welcome, guest | Sign In | My Account | Store | Cart

interleave bits (aka morton-ize aka z-order curve) (Python recipe) by Romain Dartigues
ActiveState Code (http://code.activestate.com/recipes/577558/)

This recipe let you encode in a single number two or three numbers.

Note: this is only an adaptation of the recipes from Sean Eron Anderson and Fabian “ryg” Giesen; all credits goes to the respective authors.

Python, 50 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def part1by1(n):
        n&= 0x0000ffff
        n = (n | (n << 8)) & 0x00FF00FF
        n = (n | (n << 4)) & 0x0F0F0F0F
        n = (n | (n << 2)) & 0x33333333
        n = (n | (n << 1)) & 0x55555555
        return n


def unpart1by1(n):
        n&= 0x55555555
        n = (n ^ (n >> 1)) & 0x33333333
        n = (n ^ (n >> 2)) & 0x0f0f0f0f
        n = (n ^ (n >> 4)) & 0x00ff00ff
        n = (n ^ (n >> 8)) & 0x0000ffff
        return n


def interleave2(x, y):
        return part1by1(x) | (part1by1(y) << 1)


def deinterleave2(n):
        return unpart1by1(n), unpart1by1(n >> 1)


def part1by2(n):
        n&= 0x000003ff
        n = (n ^ (n << 16)) & 0xff0000ff
        n = (n ^ (n <<  8)) & 0x0300f00f
        n = (n ^ (n <<  4)) & 0x030c30c3
        n = (n ^ (n <<  2)) & 0x09249249
        return n


def unpart1by2(n):
        n&= 0x09249249
        n = (n ^ (n >>  2)) & 0x030c30c3
        n = (n ^ (n >>  4)) & 0x0300f00f
        n = (n ^ (n >>  8)) & 0xff0000ff
        n = (n ^ (n >> 16)) & 0x000003ff
        return n


def interleave3(x, y, z):
        return part1by2(x) | (part1by2(y) << 1) | (part1by2(z) << 2)


def deinterleave3(n):
        return unpart1by2(n), unpart1by2(n >> 1), unpart1by2(n >> 2)

In my case i found useful to store two values in a single field of my database.

Usage:
>>> interleave2(800, 600)
861824
>>> deinterleave2(861824)
(800, 600)
>>> interleave3(400, 300, 12)
52501888L
>>> deinterleave3(52501888L)
(400L, 300L, 12L)
Tags: algorithm, bits, manipulation, mathematical, mathematics