more sign twiddling, today, How to know if 2 integers have the same sign, and how to get that info FAST !
var b:Boolean = (sign(i)==sign(j)) ? true : false
to know if 2 integers have the same sign, we can do the obvious:
var equalsignB:Boolean = (j<0 && i<0)||(j>=0 && i>=0);
Can we do something faster?
If we do (i XOR j), the result gives us a number with a sign bit of 1 if i and j don’t have the same sign, 0 if they have the same sign, so we can simply shift the sign bit to the right (>>31)
(j^i)>>31
,
with this, the result is -1 if they don’t have the same sign, 0 if they have the same. By just adding 1 to the formula, we get what we are looking 1 if they have the same sign, 0 otherwise.
finally:
var equalsignB:Boolean = 1+(j^i)>>31;
As usual, I like to write an assembly version, and maybe make it a little bit faster:
//equalsignB = 1+((j^i)>>31); __asm ( GetLocal(i), GetLocal(j), BitXor, PushByte(31), ShiftRight, PushInt(1), AddInt, ConvertBoolean, SetLocal(equalsignB) );
We can also just test if the XOR value is negative or positive:
var equalsignB:Boolean =((j^i)>=0);
Rewritten in assembly:
//equalsignB = ((j^i)>=0); __asm ( GetLocal(i), GetLocal(j), BitXor, PushByte(0), GreaterEquals, SetLocal(equalsignB) );
var v:int = (sign(i)==sign(j)) ? 1: 0
Now, if we don’t want a boolean as a result, but an int, we can modify all the above versions:
var equalsign:int = (j<0 && i<0)||(j>=0 && i>=0) ? 1 :0; //1
for the xor version, it stays the same:
var equalsign:int = 1+((j^i)>>31)
assembly version:
//equalsign = 1+((j^i)>>31); __asm ( GetLocal(i), GetLocal(j), BitXor, PushByte(31), ShiftRight, PushInt(1), AddInt, SetLocal(equalsign) );
And finally, the sign test of (j XOR i)
equalsign = int((j^i)>=0);
which can be rewritten in assembly:
//equalsign = int((j^i)>=0); __asm ( GetLocal(i), GetLocal(j), BitXor, PushByte(0), GreaterEquals, ConvertInt, SetLocal(equalsign) );
Results..
Great, so if you need the result as an int or as a boolean, we have few options, which one is the fastest?
Our bit twiddling version works great, and no need to do tricky assembly code to get improved results.
Note that the conversion of the slowest version : equalsignB:Boolean = (j<0 && i<0)||(j>=0 && i>=0) to assembly
gives us really good result, proof once again that we can’t always rely on the compiler for best results.
What do you get?
Code
Here the full code:
protected function intEqualSignTest():void { var i:int = 0; var j:int = 0; var equalsign:int; var equalsignB:Boolean; const REPS:int = 4000; var time1:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) { //both <0 or both >=0 => 1 equalsign = (j<0 && i<0)||(j>=0 && i>=0) ? 1 :0 } } var time2:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) { equalsign = 1+((j^i)>>31) } } var time3:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) { //equalsign = 1+((j^i)>>31); __asm ( GetLocal(i), GetLocal(j), BitXor, PushByte(31), ShiftRight, PushInt(1), AddInt, SetLocal(equalsign) ); } } var time4:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) { //equalsign = int((j^i)>=0); __asm ( GetLocal(i), GetLocal(j), BitXor, PushByte(0), GreaterEquals, ConvertInt, SetLocal(equalsign) ); } } var time5:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) { //both <0 or both >=0 => true equalsignB = (j<0 && i<0)||(j>=0 && i>=0); } } var time6:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) { equalsignB = 1+((j^i)>>31); } } var time7:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) { //equalsign = 1+((j^i)>>31); __asm ( GetLocal(i), GetLocal(j), BitXor, PushByte(31), ShiftRight, PushInt(1), AddInt, ConvertBoolean, SetLocal(equalsignB) ); } } var time8:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) { //equalsignB = ((j^i)>=0); __asm ( GetLocal(i), GetLocal(j), BitXor, PushByte(0), GreaterEquals, SetLocal(equalsignB) ); } } var time9:uint = getTimer(); startTest(); setTest( "if both<0 || >=0" , "int_equalsign to int", time2-time1 ); setTest( "1-((j^i)>>>31)" , "int_equalsign to int", time3-time2 ); setTest( "asm v1" , "int_equalsign to int", time4-time3 ); setTest( "asm v2" , "int_equalsign to int", time5-time4 ); setTest( "if both<0 || >=0" , "int_equalsign to bool", time6-time5 ); setTest( "1-((j^i)>>>31)" , "int_equalsign to bool", time7-time6 ); setTest( "asm v1" , "int_equalsign to bool", time8-time7 ); setTest( "asm v2" , "int_equalsign to bool", time9-time8 ); endTest(); }
Leave a Reply