Solved, AS3 - fast way to implement simple 90 degrees rotation? page 2

Originally posted by ErlendHL:

Also what is ^?

http://help.adobe.com/en_US/FlashPlatform/reference/actionscript/3/operators.html#bitwise_XOR

Alright, but it still doesn’t make much sense to me :/ Isn’t there any way to optimize it and still keep the old logic?

Originally posted by ErlendHL:

Alright, but it still doesn’t make much sense to me :/ Isn’t there any way to optimize it and still keep the old logic?

no. and this logic performs identical actions as the old one, except it’s much faster.

also, there isn’t something wrong with the logic; the abs is much faster than the if statements, by a factor of over 100×. it’s well worth the gain.

also, XOR: eXclusive OR. the logic is a != b for each bit; so for true/true you get false; for true/false you get true. etc.

7 is 111 in binary; 6 is 110 7 ^ 6 is 001; or 1 in decimal. m is either 0 or -1; the highest bit (the 32nd one) is duplicated by the >> operator. so a value that is negative (the highest bit is set) will produce the value -1 because -1 is 11111111 11111111 11111111 11111111 in binary (twos compliment); so -1 ^ anything simply inverts all of the bits. a negative number is converted into a positive one like: -2 ^ -1 = 1; from there i subtract -1 (same as adding 1) to correct for the offset. also, 0 ^ anything is always the input; 0 ^ 2 = 2; etc.

Hm, and all this you just plan yourself? It’s really mindfuckingly advanced.
I don’t understand how _y >> 31 can be -1, and how is -1 11111111 11111111 11111111 11111111 in binary? Isn’t it like 10000000 0000000[…….] 0000001 or something?

Also I’m not sure if _y = yO - y; and _x = xO - x; always is the right thing to do, because setting the new x uses either y or x depending in the rotation, also when setting the new y.

_x = 19 - y; and _x = 19 - x;.

-1 is 11111111 11111111 11111111 11111111 in binary because they’re represented as two’s-complement numbers. The left-most bit is the sign bit. If we call it s, it basically changes the rest of the number by adding -s*2^(n-1), where n is number of bits. It does not simply negate it. For example, if we had 01111111 11111111 11111111 11111111, that would be int.MAX_VALUE or 2^31-1. In that case, -s*2^(n-1) evaluates to 0 (because the leading bit is 0) and doesn’t affect the number. Now, change the first bit to a one and you get 2^31-1 – 1*2^(32-1) which clearly equals -1. I suck at explaining this :P

Alright, I understand (also wikipediaed it)
I’ll do it the way skyboy said then.. tomorrow :)

Originally posted by ErlendHL:

Also I’m not sure if _y = yO - y; and _x = xO - x; always is the right thing to do, because setting the new x uses either y or x depending in the rotation, also when setting the new y.

_x = 19 - y; and _x = 19 - x;.

good point. x and y look too similar if you’re tired; this corrects that behavior:

var _y:uint, _x:uint, y:uint, x:uint, m:uint, // m(ask) is scratch space for below inline calculation
    xO:uint = 19 * ((rotation >> 1) ^ (rotation & 1)), // if rotation == 1 || rotation == 2
    yO:uint = 19 * (rotation >> 1), // if rotation == 2 || rotation == 3
    dMap:Vector.<Boolean>, s:int = int(xO != yO);
target.lock();
for (; y < 20; ++y) {
    dMap = deathMap[y];
    for (x = 0; x < 20; ++x) {
        if (dMap[x]) {
            _y = yO - (x * s | y * (s ^ 1));
            (m = _y >> 31), _y = (m ^ _y) - m; // Math.abs
            _x = xO - (y * s | x * (s ^ 1));
            (m = _x >> 31), _x = (m ^ _x) - m; // Math.abs
            target.setPixel(_x, _y, blackWhite(target.getPixel(_x, _y)));
        }
    }
}
target.unlock();

Alright, I’m starting to understand things
But how is rotation >> 1 the same as rotation == 2 || rotation == 3? Especially when (rotation >> 1) ^ (rotation & 1) is (rotation >> 1) ^ (rotation & 1)?
And why ++y and ++x? Is it faster?
Btw is (s ^ 1) faster than !s?

_y >> 31, when shifting bits, are the bit that gets “shifted out” placed at the start of the int? I don’t understand what answer you get from y >> 31

It has to do with the rounding effect of using bitshift

1 >> 1 == 0 //half of 1 is 0.5 rounded down to 0

2 >> 1 == 1 //half of 2 is 1 rounded down to 1

3 >> 1 == 1 //half of 3 is 1.5 rounded down to 1

4 >> 1 == 2 //half of 4 is 2 rounded down to 2

5 >> 1 == 2 //half of 5 is 2.5 rounded down to 2

So we can use bitshift to cleverly identify if rotation is 2 or 3 because they both result in 1.

Oh alright Drakim thanks!
But isn’t _y >> 31 in most cases 0? Oh wait! It will get the first bit, which is the sign, so it checks if the value is negative!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Alright!

Edit: But about the first thing I mentioned right before Drakim’s post,

Originally posted by ErlendHL:

Alright, I’m starting to understand things
But how is rotation >> 1 the same as rotation == 2 || rotation == 3? Especially when (rotation >> 1) ^ (rotation & 1) is (rotation >> 1) ^ (rotation & 1)?

And what Drakim said, that means that the second sentence, the one where you set xO, actually checks if rotation == 1 || rotation == 2 || rotation == 3 doesn’t it?

Originally posted by ErlendHL:

But how is rotation >> 1 the same as rotation == 2 || rotation == 3? Especially when (rotation >> 1) ^ (rotation & 1) is rotation == 1 || rotation == 2?

rotation is an int. 1 has a value of 01 2 has a value of 10 3 of 11
1 >> 1 is 00 2 >> 1 is 01 3 >> 1 is 01

for xO you have effectively rotation == 1 != rotation == 2 which will be true on 1 and 2, but false on 3 and 0. for yO you have rotation == 2 || rotation == 3 (since the bit in position 2 from the right is true(1))

Originally posted by ErlendHL:

And why ++y and ++x? Is it faster?

++x is not faster, but it’s better practice. in C++ the behavior of the two may differ on abstracted complex objects so it’s important to use ++x where ever you do not need the value of x before the increment. even if you never use C++, it’s a good habit and better practice.

Originally posted by ErlendHL:

Btw is (s ^ 1) faster than !s?

s ^ 1 returns an int while !s returns a Boolean. you can’t multiply by a Boolean, the compiler yells at you.

Originally posted by ErlendHL:

_y >> 31, when shifting bits, are the bit that gets “shifted out” placed at the start of the int? I don’t understand what answer you get from y >> 31

>> shifts bits to the right (hence the arrows pointing to the right; and the operator being called right shift). the left-most bit, the sign bit, is duplicated to every position that is vacated. 31 vacates all bits, so if the sign bit is 1(negative), the end result is -1 but if the sign bit is 0(positive) the end result is 0. for two rotation directions each, _x >> 1 and _y >> 1 equal -1, and the other two they equal 0.

>>> is the unsigned right shift operator. all bits are shifted to the right, including the sign bit. -1 >>> 1 is int.MAX_VALUE becaue >>> pads the left bits with 0, always.

<< is the left shift operator; it shifts bits to the left and pads on the right with 0. there is no unsigned version of this. 1 << 31 is int.MIN_VALUE

^ is XOR; equivalent to using != on each bit in the number. 2 ^ 1 is 3 and 3 ^ 1 is 2

& is AND; equivalent to using == on each bit in the number. 2 & 1 is 0 and 3 & 1 is 1

| is OR; equivalent to using || on each bit in the number. 2 | 1 is 3 and 3 | 1 is 3

Thank you very much!

So _y >> 31 returns either 0 or -1. I guess then _y >>> 32 returns 0 or 1?
Anyway I’m just gonna implement this now.

Alright, seems like rotation 1 and 3 are swapped.

I can’t currently find any errors in the code – it looks nice. It’s taking pretty long time for me to figure out whether something of that code is right or wrong lol, have to think hard about what every bitwise operation does and how they act together, but I guess it’s easier for you skyboy :P

Edit: I switched xO and yO of course ;) now it works, thank you!

Originally posted by ErlendHL:

Thank you very much!

So _y >> 31 returns either 0 or -1. I guess then _y >>> 32 returns 0 or 1?
Anyway I’m just gonna implement this now.

arguments to >> >>> << are modulo’d to between 0 and 31. there are only 32 bits, and anything greater than 31 is technically invalid.

Originally posted by ErlendHL:

have to think hard about what every bitwise operation does and how they act together, but I guess it’s easier for you skyboy :P

i’ve been at it longer :P

Is there are reason why there’s no implementation for shifting doubles?

Originally posted by BigJM:

Is there are reason why there’s no implementation for shifting doubles?

because they’re floating points. shifting them is either a very bad idea, a bad idea, a dumb idea, or impossible to implement in a desirable way. depending on context, use case, and implementation.

you can, however, convert them to int then shift them and convert them back.

I know very little about binary arithmetic, so that may have been a dumb question :P

Originally posted by BigJM:

I know very little about binary arithmetic, so that may have been a dumb question :P

double is implemented in something like the following:

[sign bit](1)[exponent](11)[significand](52+1)
the sign bit is just true/false for saying the number is negative.
the exponent is the power of 10 that you raise the significand to

the significand is rather complex.
there’s an implied bit (not certain how it works) that makes the value equal to 1
the remaining 52 bits describe the value, each one half of the previous bit, so:
(from the left) bit 1 is equal to 0.5, 2 is 0.25, 0.125, … 0.0000000000000002220446049250313080847263336181640625

all together, they add up to equal .999…, approximately. this is what causes all of those rounding errors and such you hear about, or experience.

there are also special values, such as the exponent and significand being 0 representing the two 0s (-0/+0) the exponent equaling (unsigned) 2047 give you Infinity(significand 0), -Infinity(sign bit set), quiet NaN and signaling NaNs (both with a non-0 significand)