If you ever wanted a reason to use a modern langauge...

[Mr_Light]

tbh my first answer was "what's that operator again" too. I gues I've should have picked up the whole 6502 days hint. this is a funny one for first year freshmen.

I'm afraid I'd hit the reject pile.

[swpalmer]

Oh oh oh.. I would pass! ... but then I would ask for too much money and Jeff would throw my résumé in the bin

[Jeff]

I dont think I've ever used  ^= before so I looked it up in my Java book.

Its not a common  operator so I tell then its XOR-assignment if they don't know

Games published by our own members! Check 'em out!

[Jeff]

Rememebr folks, the point is not to get the right anser necessarily.

Its just that watching people attack it gives me insight  into how they are going to attack OTHER problems they've never seen ebfore.

ANd thats the most fundemental skill set I know for a good engineer-- being able to tackle new problems you've never seen before.

[CaptainJester]

At first, I thought it zeroed both A.  But found out the true answer by trying it in code.

[oNyx]

>But found out the true answer by trying it in code.

Tsk.

You should solve that in your head, with your fingers (counting in binary is bad for your finger joints tho) or with pen&paper. (Or well, already know about it... heh.)

A 0101
B 1100

A^=B

A 1001
B 1100

B^=A

A 1001
B 0101

A^=B

A 1100
B 0101

Thats everything. Once you take it apart its very easy to grasp.

[Mr_Light]

Thats everything. Once you take it apart its very easy to grasp.

I thought the actual thing to note was that the value of a is at the end of the code the value of b and vice versa without using a (precious?) additional help var

[Jeff]

That is correct, that it is a two-register swap.

very useful on processors like the 6502 that only had 2 registers and each had special uses.

[oNyx]

Thats everything. Once you take it apart its very easy to grasp.

I thought the actual thing to note was that the value of a is at the end of the code the value of b and vice versa without using a (precious?) additional help var

Obviously.

[Raghar]

IIRC IA32/64 assembly has special instruction for this. Java JIT should be also able to recognize the pattern "exchange". However most persons with experience should be able to recognize, or guess, the purpose of this pattern.

There are worse ones, for example change sign from negative to positive without if.
so A = -3 ... A = 3
   B = 3 ... B = 3

Games published by our own members! Check 'em out!

[ryanm]

Square and then square root?
Bit-twiddling?

[Markus_Persson]

IIRC IA32/64 assembly has special instruction for this. Java JIT should be also able to recognize the pattern "exchange". However most persons with experience should be able to recognize, or guess, the purpose of this pattern.

There are worse ones, for example change sign from negative to positive without if.
so A = -3 ... A = 3
   B = 3 ... B = 3

Ooh!
I had never heard about that one before, so I tried figuring it out:

1   2   3

int val = random.nextInt(); int sign = ((val&0x80000000)>>>31); int val2 = (val^(0xFFFFFFFF*sign))+sign;

Probably not optimal, but fun. :-D


edit:

Cleaner version with less bit twiddling.

1   2   3

int val = random.nextInt(); int sign = ((val&0x80000000)>>>31); int val2 = val*(1-sign*2);

edit again:

Heh. Even easier.

1   2

int val = random.nextInt(); int val2 = val*(1-(val>>>31)*2);

[Anon666]

IIRC IA32/64 assembly has special instruction for this. Java JIT should be also able to recognize the pattern "exchange". However most persons with experience should be able to recognize, or guess, the purpose of this pattern.

There are worse ones, for example change sign from negative to positive without if.
so A = -3 ... A = 3
   B = 3 ... B = 3

Never come across that one before.

I think this should work?
Dunno if its the optimal solution though.

1   2   3

int a = random.nextInt(); final int sign = a>>31; a = (a-(sign&1)))^sign;

:edit:

he, beaten to it.
Slightly different algorithm though =)
No multiplies either

[Markus_Persson]

Yes, and yours is faster!

Math.abs(): 17.61743 ns
My way: 6.5100017 ns
Your way: 5.472977 ns


This is fun, in a geeky way!

[Anon666]

lol, is that with the code inside a method?

[Markus_Persson]

Even faster:

1	a = (a^(a>>31))-(a>>31);

4.3739724 ns

Storing the sign in a final int is actually SLOWER on my jvm (1.5.0_06, client).


And, no, it's not including a method call. =)
I set up an int[] full of random integers, then do four for loops like this:

1   2   3   4   5   6   7   8   9   10

int res = 0; long pre = System.nanoTime(); for (int i = 0; i < vals.length; i++) {     int a = vals[i];     a = (a^(a>>31))-(a>>31);     res += a; } long post = System.nanoTime(); Sytem.out.println((post - pre)/(float)vals.length + " ns");

The res values are then compared to each other to make sure they all get the same result.
Of course, this is all done several times to make sure the code has a chance to warm up.

Edit:
Just to clarify, the ONLY thing that changes in the loops is the middle row. (ie the one that says "a = (a^(a>>31))-(a>>31);" above)
This makes sure the loop overhead is the same.

[swpalmer]

You should stick these in a final method and compare with Math.abs()...   Then if it is still faster submit a performance enhancement to Mustang

[Markus_Persson]

Math.abs: 17.01518 ns

1   2   3

public static int abs(int a) {     return (a < 0) ? -a : a; }

Foo.abs: 4.990932 ns

1   2   3   4

public static int abs(int a) {     return (a^(a>>31))-(a>>31); }

That's.. quite a lot faster.

[Anon666]

Sweet! I like your further optimised version!
I presume that is the optimal solution.

[Mark Thornton]

Sweet! I like your further optimised version!
I presume that is the optimal solution.

It may not be so efficient on processors that lack a fast shifter. While many processors will do a 31 bit shift in 1 or 2 clock cycles some require 31 clock cycles.

[kappa]

You should stick these in a final method and compare with Math.abs()...   Then if it is still faster submit a performance enhancement to Mustang

yup gotta agree with that, markus u gonna submit it?

[Markus_Persson]

Is Math.abs() really ever even close to being a bottleneck? ;-)

If someone else wants to submit it, go for it.

[Anon666]

Is Math.abs() really ever even close to being a bottleneck? ;-)

Doubtful, though Java is renown for having slow trig.

I realize this is in part due to the accuracy specifications,
but any unnecesary slowdowns in core methods (such as abs()) are always going to have a knock-on effect when they are relied upon in higher level functionality.

[Markus_Persson]

That is true. :-)

Now we just need to figure out a fast abs for floats and doubles.

[Jeff]

Is Math.abs() really ever even close to being a bottleneck? ;-)

Doubtful, though Java is renown for having slow trig.

See the gems section of my FAQ for a way to improve this.

[Jeff]

Speaking of which has anyone timed this out against Math.abs(int) ?

If its faster, I'll add it to the Gems section

[Raghar]

That is true. :-)

Now we just need to figure out a fast abs for floats and doubles.

That's easy, actually it's much easier than for integers. Just use one AND, and you are done. ^_^
Of course I asume you are using SSE2 registers for all floating point work.

[Markus_Persson]

Speaking of which has anyone timed this out against Math.abs(int) ?

If its faster, I'll add it to the Gems section

Yes, see my post a few post backs.
Even when in a method, the hack runs at about 30% of the speed of Math.abs(int)

That's a speedup of ~250%!

[oNyx]

Wow this thread actually became useful again. What a surprise

[.uj]

Wow this thread actually became useful again. What a surprise

But awfully dull isn't it. The coolest accessory you can wear at this forum probably is blinkers. 

Good luck with Math.abs! Once you got that optimized everybody will start using Java I'm sure.