Calculating morton code

Question

i am trying to interleave(For calculating morton code) 2 signed long numbers say x and y (32 bits) with values

case 1 :

x = 10;  //1010
y = 10;  //1010

result will be :

11001100

case 2:

   x = -10;
   y = 10;

Binary representation are,

x = 1111111111111111111111111111111111111111111111111111111111110110
y = 1010

For interleaving ,i am considering only 32 bit representation where i can interleave 31st bit of x with 31st bit of y , using the following code,

signed long long x_y;
for (int i = 31; i >= 0; i--)
        {

                    unsigned long long xbit = ((unsigned long) x)& (1 << i);
                    x_y|= (xbit << i);

                    unsigned long long ybit = ((unsigned long) y)& (1 << i);

                    if (i != 0)
                    {
                                x_y|= (x_y<< (i - 1));
                    }
                    else
                    {
                                (x_y= x_y<< 1) |= ybit;
                    }
        }

The above code works fine ,if we have x positive and y negative but the case 2 is failing ,Please help me ,what is going wrong? The negative numbers uses 64 bits ,whereas positive numbers uses 32 bits.Correct me if iam wrong.

Answer 1

I think below code work according to your requirement,

Morton code is 64 bits and we are making 64 bit number from two 32 bits numbers by interleaving. Since numbers are signed ,we have to consider negative numbers as,

if (x < 0) //value will be represented as 2's compliment,hence uses all 64 bits
    {
        value = x; //value is of 32 bit,so use only first lower 32 bits 
        cout << value;
        value &= ~(1 << 31); //make sign bit to 0,as it does not contribute to real value.
    }

similarly do for y.

Following code does the interleaving,

unsigned long long x_y_copy = 0; //make a copy of ur morton code
//looping for each bit of two 32 bit numbers starting from MSB.
    for (int i = 31; i >=0; i--)
    {
        //making mort to 0,so because shifting causes loss of data
        mort = 0;
        //take 32 bit from x
        int xbit = ((unsigned long)x)& (1 << i);
        mort = (mort |= xbit)<<i+1;    /*shifting*/
        //copy  formed code to copy ,so that next time the value is preserved for appending
        x_y_copy|= mort;
         mort =0;
        //take 32nd bit from 'y' also
        int ybit = ((unsigned long)y)& (1 << i);
        mort = (mort |= ybit)<<i;
        x_y_copy |= mort;
    }
    //this is important,when 'y'  is negative because the 32nd bit of 'y' is set to 0 by above first code,and while moving 32 bit of 'y' to morton code,the value 0 is copied to 63rd bit,which has to be made to 1,as sign bit is not 63rd bit.
    if (mapu_y < 0)
    {
        x_y_copy = (x_y_copy) | (4611686018427387904);//4611686018427387904 = pow(2,63)
    }

I hope this helps.:)