Wrestling with bit shifts

[Rolig Loon]

This one's for Void. I'd ask it in a private note, but I kind of suspect I'm not the only person who might be curious about the answer.

I have really put off understanding bit shift logic in LSL for too long, and am trying to make sense of it.  This short script, based on a suggestion in http://community.secondlife.com/t5/LSL-Scripting/RFC-single-script-multi-room-rental-box/td-p/996659 works, but I cannot figure out why it does for the life of me.  Can you walk me through the logic?  In particular, how do you know how far to shift the bits in vIntBgn? (I get the same result if I left shift Pos.x  by 20, or 22 or 23 bits, for example).  And how in heaven's name do you decide what the mask values (255?  8191???) should be in vPosGoto? 

ETA:  Ah, wait.  I do see where the mask values come from. 255 =  11111111 ; 8191 = 1111111111111 , but why mask 8 and 13 bits respectively?  Still working on the rest, though.......

default
{
    touch_start(integer total_number)
    {
        vector Pos = llGetPos();
        integer vIntBgn = (llFloor( Pos.x ) << 21) + (llFloor( Pos.y ) << 13) + llCeil( Pos.z );
        vector vPosGoto = < (vIntBgn >> 21) + 0.5, (vIntBgn >> 13 & 255) + 0.5, (vIntBgn & 8191)>;
        llSay(0, (string) Pos + " = " + (string)vIntBgn + " = " + (string)vPosGoto);
    }
}

 Short of asking you to write a handy manual, Void, can you recommend a primer than will help me figure out this stuff?

[Void Singer]

heh experience mostly.... but here's how it breaks down

4096 (max z height for teleports in a region) is "1 0000 0000 0000" in binary (that 13 bits in the field, the spaces are just to make it readable). if you are lazy, and I am, you punch the number into windows calculator and make sure it's in scientific mode and check the binary button to convert, then count places.

255 (the maximum integer x and y coordinates in a region when rounding down) is "1111 1111" in binary (8 places). so we shift up 13 (to avoid overlapping with the z value) which gives us thirteen zeros after whatever value for Y we started with... when inserting X we added 8 more zeros behind that so that we didn't overlap either the Y or Z areas...

in memory it looks a bit like

Xxxx xxxx << 13 =000X xxxx xxx0 0000 0000 0000 0000 0000Yyyy yyyy << 13 =0000 0000 000Y yyyy yyy0 0000 0000 00000000 0000 0000 0000 000Z zzzz zzzz000X xxxx xxx0 0000 0000 0000 0000 0000 +0000 0000 000Y yyyy yyy0 0000 0000 0000 +0000 0000 0000 0000 000Z zzzz zzzz zzzz =000X xxxx xxxY yyyy yyyZ zzzz zzzz zzzz

 if you notice the zeroes on the lef thand side, those are unused bits, which is why you can shift x up a bit more and still get the right result if you shift back the same amount.

shift in binary works basically the wame way that "e" does in scientific notation.... it shifts the place (or decimal point if you prefer), effectively multiplying or dividing the number by it's base however many times you tell it to. so just like 1e2 == 100, 1<<2 == 100 (in binary which makes it 4 in decimal, because you multiply the starting number by the base as many times as you are told.)

 

so how did I figure out 8192? well I could use the calculator and punch in a string of thirteen 1's, but since I know that it's 1 higher than if I had all the proceeding digits as one, I just doubled 4096 and subtracted 1 to get the decimal number that was a string of thirteen 1's in binary.... why did I need that? because masks (when you use the "&" operator) only read the of the the value, where there is a 1 in the mask... so it acts like a "check these spots and not the other ones" instruction, so that I only read the part that I set up for that value. kind of like punching out holes on a piece of paper and then laying it on top of a book page. the paper is the mask, the holes are the 1's, and the book page is the source.

 

there were also two other considerations I included in that snippet... z values were rounded up so that at worst you'd be <1m above the original target, which is better than showing up low in the floor and falling through. the X/Y values were rounded down so that I could usee 0-255 instead of 0-256, so it only needed 8 bits each (I would have done the same for z and used 12 bits except for the bad thing of falling through), and then added .5m back so that it wouldn't  be offset as much for upper half round downs (>0.5), and will be no closer than 0.5m to the region border.

 

[Rolig Loon]

Lovely.  Thank you, Void!

It is so much easier to work through new territory when you have an example to do reverse engineering on.  I sat here this morning, puzzling over that snippet you dropped in the other thread, and could almost see where it was going.  I got lost wondering why you shifted 13 and 8, and especially why you then masked with 8191later.  Your explanation clears it all up, though.

Like everyone else, I tend to carry boolean variables around to use as switches or to remember which whitelisted people are in-world  or whatever.  I'm slowly recognizing that if I know what I'm doing, I can string a bunch of those booleans together ina single variable and use bit shifting and masking to poke at parts of it at a time.  Exercises like this one help me get closer to doing that.

[Void Singer]

ps 20 in the original example could bork, but only in 25% of the possible cases.

also beware of >>. it seems the same but it has an important difference. << pads with 0's, >> pads with whatever bit was on the leftmost to start with... there's good reason for it but it can be confusing... the leftmost bit is actually the sign bit for signed integers (which is what we have in LSL)... keeping the sign the same for shifts is usually important, so that's why it works that way. in other languages you actually have 4 shifts... a set of each direction that pads with zero, and a set that pads with whatever the previous end bit was.

[Rolig Loon]

Thanks for mentioning that.  I would never have guessed it, and I know I would have bumped my nose on it sooner or later.

[Ashasekayi Ra]

Thanks for that detailed explanation. ^^ I've always been interested in how to use bit shifting. Your example and explanation cleared up a lot of confusion.

@Roliq: Thanks for posting the question. I thought the same thing when I saw that thread.