The >> operator

I saw an example of the >> operator and can't figure out why it is correct.

result = 5 >> 1
// result = 2

I understand that the >> operator divides the number on the left by the the number on the right twice. So why is the result 2 and not 5?

Thank you!

Sabia

It's a bitwise operator, not division twice. ">> 1" moves bits one bit to the right, so 5 (101) becomes 2 (010) when you shift bits to the right. If you wrote result = 5 >> 2, you should get (001) = 1. The " <<" operator does the same thing, but shifting to the left, so result = 5 << 1 should give you (1010) = 10.

Yup.. Some more examples:

01110 >> 1 = 00111
01110 >> 2 = 00011

00111 << 1 = 01110
00111 << 2 = 11100

>> is "all bits move to the right!" and << is "all bits move to the left!"

Thank you for your speedy responses. I've heard of bitwise operators but had forgotten about them. The question I asked arose from a page on integer arithmetic in "Creating Your Own World." on page 105. It seems to be describing another type of operator. I need to find a forum for the book. I'll keep looking at Wiley.

Thanks again because that info is valuable to me (a new scripter) as well.

Sabia

Well, doing a >> 1 is sorta the same as doing / 2. With integer math, 5/2 does indeed equal 2.

Feel free to ask script questions here. We may not have the book or understand references to it but there are some clever folks about.

Mathematically,

x >> n = x / llPow(2,n)

x << n = x * llPow(2,n)

well almost...
where x and y are positive integers
-1 >> y will always be negative one

programatically that'd be
(x >> y) == uShft( x, y )

uShft( integer x, integer y ){
integer r = x / llPow( 2, y ); //-- fractions are discard in integer math
return r - ((r == 0) && (x < 0));
}

also watch out for shifting entries that will go beyond min/max integer when using << because they can change sign and tend towards zero where "x << (y < 31) " is always zero.

That's the answer. I misunderstood that aspect of integer arithmetic. I never did find a Wiley forum for the book so I'm glad you could clarify this for me. Thank you all again!

Sabia

That's because the C implementation of >> is a SAR/ASR instead of a SHR/LSR, since there are only signed integers in LSL. -1 >> y == -1 is a traditional pathological artifact of SAR/ASR. It is good to keep in mind, though.



Yeah, was really pointing out the math behind it, rather than the code; just displaying the math in code form since displaying it in math-like symbols would be more confusing.

for those playing at home, ASR = arithmetic shift right and LSR = logical shift right...

the difference only matters if the number is signed. and then only on the shift right operator.
essentially the rightmost bit is dropped, and the leftmost bit is copied into the leftmost place.... (signed zero systems (which we don't have in lsl integers) would yield negative zero as expected in ASR)

Well, actually, no.. ASL is a different operation than LSL, too, for negative numbers. Integers wreak havoc with shift operations when you're trying to keep a semblance of sanity with respect to arithmetic. If you have an integer which is something like 10110110 and use <<, it should retain the sign, too, resulting in 11101100, rather than 01101100.

Basically, the only safe assumption when it comes to the mathematics behind it is to deal with positive integers or whole numbers (ie, x >= 0).

For some of us playing at home, this sounds like trying to decide how many angels can dance on the head of a pin. Fascinating, in a distant sort of way. Of course, I've never had conversations like this in my own discipline ....

It's not "pathological", and the behavior of large negative numbers is perfectly consistent with the behavior of large positive numbers. 01000000 << 1 should "stay positive" by your logic, too, instead of becoming a large negative number 10000000.

Something I don't understand, what's the point of bit shifting in LSL?

Nyx, as one who uses math but is not a mathematician, I predict that the experts in the crowd will say that your question is like a blind person asking what the point of color filters in photography is. It's hard to explain in a way that isn't uncomfortably esoteric to a layman. Hence my flippant comment a couple of posts back. I'm always pleased to get a glimmer of what the pros mean, even if it doesn't seem useful to me right away.

I'm not aware of any languages that implement sign retention for ASL offhand (LSO/MONO surely doesn't)... usually #>range==undefined

EDIT, I take it back VHDL does, Ada might (but I'm not going to go check) although anyone reading this and toying with either of those languages is prolly not paying much attention to what we're saying =)

@Nyx/Rolig
well the an obvious answer is that it allows faster multiplication and division by powers of 2 than the multiplication and division operators, but another use would in using less constants to factor out different base numbers, or storing multiple smaller numbers in a larger integer.

and example of the later, which stores a web color code in an integer, instead of a vector (so that you could, say, pass it in a start parameter) goes something like this...

//-- assume input is a vector with zero to 255 ranges for each value
integer uColor2Integer( vector vColWeb ){
return (vColWeb.x << 16) + (vColWeb.y << + vColWeb.z;
}

//-- this shows the same constant being used so after the fact so that differnt ones don't have to be used beforehand.
vector vInteger2Color( integer vIntCol ){
integer vIntConst = 255; //-- 0xFF
return < (vIntCol >> 16) & vIntConst, (vIntCol >> & vIntConst, vIntCol & vIntConst>;
}

EDIT:
another use if checking if a number is negative, using "x >> 31" (-1 if negative, 0 if positive)
which is faster than (x < 0)

Now THAT's nice. Multiplying and dividing by powers of two was the only obvious thing on my mind, although even there bitwise operations wouldn't be my intuitive tools of choice. The business with vector manipulation, though, is cool and unexpected. I'll have to think about this a bit before I am comfortable enough with it to use it myself, but I can see the shape of it. I wouldn't have thought of using is as a way to pack and unpack numbers in a larger one. I learned something today. Thanks, Void.

you can actually pack one more 0-255 number in there, and it'd be the same as several uncompressed image formats (the extra field is alpha transparency). or even sign the numbers, pack mini-floats, pack different ranges of numbers, allow binary floats... it's a matter of putting them together where you know you want them, and tearing them apart in the reverse order.

PS
I forgot to cast the vector inputs to integer... won't work otherwise... whoops

Is there a way to store two numbers in a single one? via bit shifting? if so how?

Sure, you can store two 16 bit numbers in a 32 bit number. Or two 10 bit numbers and a 12 bit number (say, points in the old building range of a sim to 1/4 meter precision). Or five six-bit values with two bits left over (eg, packing uppercase-only ASCII into a symbolic name field)...

Based on Void's example, to combine two 16 bit values:

integer TwoIntoOne (integer x, integer y)
{
    return (x << 16) + y;
}

list TwoOutOfOne (integer x)
{
    return [x >> 16, x & 0xFFFF];
}

default
{
    state_entry()
    {
        llOwnerSay (llList2CSV (TwoOutOfOne (TwoIntoOne (123, 456))));
    }
}

This works in LSLEditor. I don't know if &ing is the most efficient method to use when extracting the numbers.

ETA: and would it be more efficient to combine the numbers using (x << 16) | y?

Since it's an arithmetic shift, you want to mask the original 16 bit X as well.

return [(x >> 16) & 0xFFFF, x & 0xFFFF];

Otherwise TwoOutOfOne(TwoIntoOne(65535,65535)) will come back as [-1, 65535].

Thanks Argent. This is way better than classroom lessons or written tutorials.

Very few do, which presents the "tip of the iceberg" of the problem. The C "standard", for example, doesn't even specify the implementation for the shift operators to be arithmetic or logical. In other words, it is implementation-dependent.

Even the underlying instruction sets don't bother to implement it properly, so the higher-level languages built on said instruction sets don't bother (generally). In the x86 instruction set, SAL/SHL are the same instruction, and SAR has been implemented from a broken paradigm since before that.

It is one of those annoying things that has become kind of a "closet skeleton" tradition in computer science. The only difference between logical shifts and arithmetic shifts is that the former just shifts bits without any consideration of their meaning, type, or format, and the latter considers said meaning, type, or format of the bits as any other arithmetic operator (add, subtract, multiply, divide, etc) does. The problem is that, due to rather sloppy implementations decades ago, and a long-time "acceptance" of such implementations without correction, it has become legacy. Even worse, in most languages, it is implementation-dependent, making for very nasty (or non-portable) code.



Please.. just.. don't.

So if I do an ASL on a floating point number it just adds one to the exponent?

I have no idea where this definition of arithmetic shift comes from. Literally, I have NO idea. I've been programming since 1s complement arithmetic was usual and non-power-of-two word sizes were common, and I've never even heard of anyone claiming that kind of formal definition of arithmetic shift before.