How to de-interleave bits (un-Mortonize) the "Obvious way" ? (In 3D)

Question

I know a similar question has already been asked. However, I have some trouble manipulating bits and can't adapt/understand the solution.

First of all I used the Interleave bits the obvious way to get myself a Morton number. I adapted it to 3D like this:

unsigned long xyz2w(unsigned int x, unsigned int y, unsigned int z)
{
    unsigned long w=0;

    for (int i = 0; i < sizeof(x) * CHAR_BIT; i++)
    {
        w |= (x & 1U << i) << i | (y & 1U << i) << (i + 1) | (z & 1U << i) << (i + 2);
    }

    return w;
}

(It seems to work fine but if you ever find an error, please let me know)

Now I would like to do the opposite operation. That is: extracting the 3 coordinates based on the Morton number.

Obviously, I tried to use the adapted-for-3D part of the previous SO topic, but I didn't understand how it works. That's why I am creating a new topic.

I am not looking for a high-performance code but for a clear and understandable code that works similar to the xyz2w function (ie "The obvious way").

`<< (i + 1)` will invoke undefined behaviour – 0___________ Mar 16 '23 at 14:58 — 0___________, Mar 16 '23 at 14:58

0___________ · Accepted Answer · 2023-03-16T16:05:00.283

Your code invokes undefined behaviour at << (i + 1)

Example implementation:

It is not efficient but I split long lines to be more easy to understand

#define MASK(x) (1ULL << (sizeof(x) * CHAR_BIT - 1))

unsigned long long xyz2w(unsigned short x, unsigned short y, unsigned short z)
{
    unsigned long long w = 0;
    for(unsigned short mask = MASK(x); mask; mask >>= 1)
    {
        w <<= 1;
        w += (!!(x & mask)); 
        w <<= 1;
        w += (!!(y & mask)); 
        w <<= 1;
        w += (!!(z & mask)); 
    }
    return w;
}
void w2xyz(unsigned long long w, unsigned short *x, unsigned short *y, unsigned short *z)
{
    *x = 0; *y = 0; *z = 0; 
    for(unsigned short bit = 0; bit < sizeof(*x) * CHAR_BIT; bit++)
    {
        *z += (w & 1) << bit;
        w >>= 1;
        *y += (w & 1) << bit;
        w >>= 1;
        *x += (w & 1) << bit;
        w >>= 1;
    }
}

int main(void)
{
    unsigned short x = 0xaabb;
    unsigned short y = 0x3355;
    unsigned short z = 0x22ff;

    unsigned long long w = xyz2w(x,y,z);
    printf("w = 0x%llx, x = %hx, y = %hx, z = %hx\n", w, x, y, z);
    x = 0; y = 0; z = 0;
    w2xyz(w, &x, &y, &z);
    printf("x = %hx, y = %hx, z = %hx\n", x, y, z);
}

https://godbolt.org/z/WPrKosG5q

Thank you for your response ! Could you please specify why it's an undefined behavior ? — Unemployed Goose, Mar 17 '23 at 07:04
because i + 1 on the last iteration is >= shifted type length. `1U << sizeof(1U)*CHAR_BIT` is undefined — 0___________, Mar 17 '23 at 09:59

How to de-interleave bits (un-Mortonize) the "Obvious way" ? (In 3D)

1 Answers1