Number Sort Algorithm

[Darrel Taylor]

Cool.

And I suppose if someone wanted to test the "Surprise", they might do something like this ...

;Initialize your hardware first

A      VAR WORD
B      VAR WORD
TempA  VAR WORD
TempB  VAR WORD

LCDOUT $FE,1

For A = 0 to 65535
    LCDOUT $FE,2,"A=",DEC A
    For B = 0 to 65535
        TempA = A
        TempB = B
        TempA = TempA ^ TempB
        TempB = TempA ^ TempB
        TempA = TempA ^ TempB
        IF (TempA <> B) OR (TempB <> A) THEN ; Test Failed
            LCDOUT $FE,1,"Test Failed",$FE,$C0,"A=",DEC A,", B =",DEC B
            STOP
        ENDIF
    Next B
Next A

LCDOUT $FE,1,"Test Passed!"
STOP

Then some 40 hours later (@ 20Mhz) [that's over 4 billion combinations],
you would no doubt see the message "Test Passed!" on the LCD.

Only a half hour into it, but it's still passing. Kinda obvious what the result will be.

Update: 43hrs, Test Passed! (obviously)
<br>

[Ioannis]

Nice routine Darrel! 40 hours to wait for "Test Passed!", wow!

Ioannis

[Darrel Taylor]

LOL,

I think I'll need those 40 hrs. just to wrap my head around why it works.

It does work, but the explanation eludes me.

@ Don't tell me, I've still got 38 hrs to go
<br>

[Darrel Taylor]

Programs still running, but I think I got the XOR thing figured out.
Not that I could explain it though.

Practicing my Flash at the same time

.. Flash moved down ..

[Bruce]

How this logic works is pretty cool. I saw this on the PIClist a few years back.

Here's how it works.

a VAR BYTE
b VAR BYTE
a = %11001100
b = %00110011

a=a^b ' a now = %11001100 ^ %00110011 which = %11111111

1 ^ 0 = 1. 1 ^ 1 = 0. 0 ^ 0 = 0.

b=a^b ' b now = %11111111 ^ %00110011 which = %11001100 (value of original a)

b now contains the original value of a.

a=a^b ' a now = $11111111 ^ %11001100 which = %00110011 (value of orignal b)

Now that b = the original value held in a, ^-oring a with b returns the orignal
value of b, in a.

Using any two values, it still works the same. Like this;

a = %11011100
b = %00110011

a=a^b ' a now = %11011100 ^ %00110011 which = %11101111
b=a^b ' b now = %11101111 ^ %00110011 which = %11011100 (value of original a)
a=a^b ' a now = $11101111 ^ %11011100 which = %00110011 (value of orignal b)

Pretty nifty way of swapping variables.

[Ioannis]

And is as fast as using swap technique!

I was wondering where I first read about it and after alot of searching, it was on a summer double Elektor issue.

Ioannis

[Darrel Taylor]

Ioannis,

Thanks for the interesting idea to ponder.

And thanks for the extra examples Bruce. But while it does show that it gets from A to B and visa versa, it didn't really answer the Why? that had me so baffeled. When I get baffeled I usually become obsessed at figuring out the why, especially when it seems like it should be so simple (Like 3 XOR's in a row).

My biggest problem was thinking it was combining the bits with the first A=A^B, then somehow pulling the bits back out with the next XOR. But none of that was making any sense.

After making the Flash, I realized that the XOR gate should really be called the "They're Different" gate, which is what the XOR does. If both inputs are the same the output is 0, if they're different, the output is 1.

Then it all made perfect sense.

The first A = A^B determines if both bits are Different or not, and stores it back in A.

Since you still know the original B value, and you know if the 2 are different then ...

If B = 1 and "They are Different" then A used to be = 0, which accounts for the B = A^B

The last A = A^B does the same thing. If they are different, and you know the new B is a 0, then the new A has to be a 1.

<OBJECT CLASSID= "clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" WIDTH="600" HEIGHT="300" CODEBASE="http://active.macromedia.com/flash5/cabs/swflash.cab#version=5,0,0,0"><PARAM NAME="MOVIE" VALUE="http://www.pbpgroup.com/files/XOR.swf"><PARAM NAME="PLAY" VALUE="true"><PARAM NAME="LOOP" VALUE="true"><PARAM NAME="WMODE" VALUE="opaque"><PARAM NAME="QUALITY" VALUE="high"><EMBED SRC="http://www.pbpgroup.com/files/XOR.swf" WIDTH="600" HEIGHT="300" PLAY="true" LOOP="true" WMODE="opaque" QUALITY="high" PLUGINSPAGE="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash"></EMBED></OBJECT>

I feel better now.
<br>