Qbasicnews.com

QbasicNews.Com => Challenges => Topic started by: Moneo on June 20, 2003, 11:12:02 PM



Title: Challenge: Identify ways to use XOR logical operator
Post by: Moneo on June 20, 2003, 11:12:02 PM
Many people never use exclusive-or (XOR). A professor at NYU, who had a PHD in Computer Science, while giving a class on "C" programming in 1985, described how it worked and then said "But who knows why you would ever use it." I almost had a fit.

Anyway, I sure you guru's can come up with many uses. But, let's keep them practical, i.e., give examples that make sense and are really useful.

Post a description of how you're using the XOR,  and then give a coding example, which will usually be one line of code. Try not to be too critical of post submitted by others, and let's keep the BS down.

Thanks,
Moneo
*****


Title: Challenge: Identify ways to use XOR logical operator
Post by: seph on June 20, 2003, 11:20:33 PM
I'm sure you can use them somehow to make a "negative image" on the screen... Like turn all colours the opposite of what they are (really just 255-colour%). Then again, I proved myself wrong.


Title: To Seph:
Post by: Moneo on June 20, 2003, 11:41:46 PM
You mean like flip the bits in color%, by doing:
Code:

color% = color% xor 255


If that's what you want, this will do it.
*****


Title: Challenge: Identify ways to use XOR logical operator
Post by: seph on June 20, 2003, 11:43:56 PM
Sure that works too. I win!


Title: Challenge: Identify ways to use XOR logical operator
Post by: LooseCaboose on June 21, 2003, 12:23:27 AM
Circuit construction, adder circuits use a XOR gate for the sum value. ie.
Code:

A B | S C
----+----
0 0 | 0 0
0 1 | 1 0
1 0 | 1 0
1 1 | 0 1

Sum(S) = A XOR B, and Carry(C) = A AND B. Although at circuit construction level usually NAND gates are used for implementation because all other gates can be constructed using just NANDs which reduces cost.

Bitflipping, as mentioned by Seph. Taking a n-bit number and XORing it against a value where all the bits are set will flip all the bits in the number.

Anytime you need to determine if one or the other, but not both of two values is set. Although many programmers will simply write this long hand:
Code:

if A then
  if  not B then ...
else
  if B then ...
end if

You will probably find many examples of code that are actualling using exclusive-or logic without using the operator directly.


Title: Challenge: Identify ways to use XOR logical operator
Post by: DrV on June 21, 2003, 12:49:09 AM
Swapping integers...
Code:
a% = 3
b% = 4
a% = a% XOR b%
b% = a% XOR b%
a% = a% XOR b%

now a% = 4 and b% = 3


Title: To LooseCaboose:
Post by: Moneo on June 21, 2003, 12:59:52 AM
Good example re circuit construction.

Your second example about doing things the long way reminds me of my favorite example which is for using a flip/flop switch.  If the switch is on (a one), you want to turn it off. If the switch is off (zero), you want to turn it on.
Code:

flipflop = flipflop xor 1

Much simpler and no need to debug several if's.
*****


Title: To drV:
Post by: Moneo on June 21, 2003, 01:24:52 AM
Excellent. Your example is a classic. You must be an assembly language programmer. In assembler you find your self doing this method to swap the contents of two registers without having to use another intermediate register or  time-consuming stores to memory.
In a sample assembly language, to swap registers a and b,  it would look like this:
Code:

a xor b
b xor a
a xor b

Basically the same thing.
*****


Title: Challenge: Identify ways to use XOR logical operator
Post by: oracle on June 21, 2003, 01:27:16 AM
Edit Button! *dissolves into tears*


Title: Challenge: Identify ways to use XOR logical operator
Post by: toonski84 on June 21, 2003, 01:28:55 AM
actually, moneo's example, by test, is an eensy weensy pee widdle bit slower than n% = 1 - n%

for 100000000 operations:
1-n: 11.19995 seconds
xor: 11.26001 seconds


Title: Challenge: Identify ways to use XOR logical operator
Post by: oracle on June 21, 2003, 01:30:54 AM
Ooooooohh...  maybe that's why no-one uses XOR  :rotfl:


Title: Re: To drV:
Post by: DrV on June 21, 2003, 01:39:28 AM
Quote from: "Moneo"
Excellent. Your example is a classic. You must be an assembly language programmer. ...


Hehe... actually, I read that in VBPJ a looong time ago, and this thread made me remember it, so I went digging around for about 20 minutes and finally found it. :)


Title: To Toonski84
Post by: Moneo on June 21, 2003, 02:03:22 AM
Ok, I'll take your word for it. the n=1-n may be faster than the
n=n xor 1, but it's not as elegant. Plus, since I learned this trick in assembler, you coudn't do the n=1-n in one instruction in most assemblers that i've seen.
But nevertheless, you win for now.
*****


Title: Challenge: Identify ways to use XOR logical operator
Post by: toonski84 on June 21, 2003, 02:42:53 AM
yeah, it's more elegant.  it also takes a 10th of a second longer to do 10 million operations.  remember:  when you're doing 10,000,000 switches, you're going to need all the speed you can get!


Title: Challenge: Identify ways to use XOR logical operator
Post by: Antoni Gual on June 21, 2003, 05:23:46 AM
XOR?   Mmmh..

1.- I  use it often to create a cheap texture
Code:

screen 13
for i=0 to 63
 for j=0 to 63
   pset(i,j),i xor j
next j,i


Edited: Nr 2 did'nt worked...


3.- The CRC algorithm is based on XOR
(Code ripped from ABC)

Code:

CRC = 0                                        'Reset for Each Text Block
FOR I = 1 TO LEN(B$)                           'Calculate for Length of Block
   ByteVal = ASC(MID$(B$, I, 1))
   FOR J = 7 TO 0 STEP -1
      TestBit = ((CRC AND 32768) = 32768) XOR ((ByteVal AND Power(J)) = Power(J))
      CRC = ((CRC AND 32767&) * 2&)
      IF TestBit THEN CRC = CRC XOR &H1021&     ' <-- This for 16 Bit CRC
   NEXT J
NEXT I
CRC16& = CRC    


4.- The sprite animation technique often suggested to newbies:

Excuse me if it's not exactly like this, you never find those darn snippets when you need them...

Code:

PUT (x,y), mask(0), XOR
PUT(X,Y),SPRITE(0),PSET


edited:

BTW: Have you ever used EQV   ?  Not me....


Title: Challenge: Identify ways to use XOR logical operator
Post by: Agamemnus on June 21, 2003, 10:44:29 AM
XOR is good, but it's a crappy name.

OR is good, AND is good. You can figure those out right off the bat.

But XOR? Come on men and women. Can't they make something cooler? Like.. "Addition of two bits without carry"


Title: Challenge: Identify ways to use XOR logical operator
Post by: Moneo on June 21, 2003, 01:10:01 PM
TO ANTONI:
Yes, the CRC calculation is probably one of the most popular uses of the XOR. The LRC (Longitudinal Redundancy Character or Check) used on some mainframe magnetic tape units, is a simpler computation that also uses the XOR, but is a less robust error checking technique than the CRC.

If anyone is interested, I have the "C" code for generating the identical CRC used by PKZIP.  I didn't concieve it, but I fixed it to work.

x EQV y
EQV stands for Equivalent, meaning it tests if the expressions X and Y are the "same", i.e., either both true or both false.
I honestly have never had an opportunity to use it.
-----------------------------------------------------------------------------------
TO AGAMEMNUS:

Regarding the name of XOR, i.e., exclusive-or. The story that I heard years ago is that a regular OR is an inclusive-or. If either of the bits is on, then the resultant bit will be inclusively on. But, for an XOR, if the bits are both on, then the resultant bit will be exclusively off.  OK, not the best definition. Note that in some languages an XOR is written as EOR.
*****


Title: Challenge: Identify ways to use XOR logical operator
Post by: HystericPoison on June 21, 2003, 07:16:04 PM
thats all too confusing for me...il just use my 300 line IF statements...at least they make sense to me


Title: Challenge: Identify ways to use XOR logical operator
Post by: LooseCaboose on June 22, 2003, 04:52:50 AM
Quote

Your second example about doing things the long way reminds me of my favorite example which is for using a flip/flop switch. If the switch is on (a one), you want to turn it off. If the switch is off (zero), you want to turn it on.

Code:

flipflop = flipflop xor 1



Err...
Code:

flipflop = !flipflop


Title: Re: To drV:
Post by: relsoft on June 22, 2003, 06:20:02 AM
Quote from: "Moneo"
Excellent. Your example is a classic. You must be an assembly language programmer. In assembler you find your self doing this method to swap the contents of two registers without having to use another intermediate register or  time-consuming stores to memory.
In a sample assembly language, to swap registers a and b,  it would look like this:
Code:

a xor b
b xor a
a xor b

Basically the same thing.
*****


I usually use XCHG. ;*)


Title: Challenge: Identify ways to use XOR logical operator
Post by: whitetiger0990 on June 22, 2003, 01:14:55 PM
i think this
Code:
flop = -flop + 1

is easier then
Code:
flipflop = flipflop XOR 1

it certainly looks shorter


Title: How to do XOR when your language doesn't have this operator?
Post by: Moneo on June 22, 2003, 02:12:02 PM
For those of us that prefer using the XOR operator, it comes as a shock when programming in another language that does not support this operator. Assuming that this language does have AND/OR/NOT operators, we can emulate an XOR as follows:
Code:

īThe following performs the same as: result = a XOR b
result = (a and not(b)) or (b and not(a))

*****


Title: Challenge: Identify ways to use XOR logical operator
Post by: DrV on June 23, 2003, 01:30:02 AM
Quote from: "Agamemnus"
XOR is good, but it's a crappy name.

OR is good, AND is good. You can figure those out right off the bat.

But XOR? Come on men and women. Can't they make something cooler? Like.. "Addition of two bits without carry"


ummm... eXclusive OR?  one or the other but not both?


Title: Sample reason for using XOR.
Post by: Moneo on June 23, 2003, 01:33:12 PM
We have posted several examples of XOR for flipping the bits in a byte. Here's a reason I had to do that.

I was writing a report program whose input file was sorted on 3 keys of variable ASCII bytes. Regardless of where a sorted file comes from, I ALWAYS sequence check it while I'm reading it, otherwise the output becomes garbage and my program looks like an idiot.

The problem was that the 2nd key was sorted descending and the 1st and 3rd keys were ascending. How do you do a sequence check in this case? Normally, you concatenate the 3 keys into a combined key and just compare each combined key to the preceding for sequence, but the descending key in the middle would not work. After thinking about it for a long while, I came up with the idea of doing an XOR with 255 (hex FF) on every byte of the descending second key before placing it into the combined key. Eureka, it worked!
*****


Title: My opinion on the scoring for this chalenge:
Post by: Moneo on June 23, 2003, 01:52:35 PM
I initiated this post so I guess I should issue some final scores. There were 11 people posting (including myself), but only 6 of us actually contibuted something, in my opinion. I have assigned 1 point for concept and 1 point for a coding example. Here are the scores in posting order for the contributors:

SEPH......................... 1 point
LOOOSECABOOSE..... 2 points
DRV........................... 2 points
TOONSKI................... 1 point
ANTONI..................... 4 points (3rd example not understood)
MONEO.....................  1 point
*****


Title: Update:
Post by: Moneo on July 03, 2003, 03:32:51 PM
In the Challenge topic re Recursion, we also saw the following use of XOR.
Code:

REM Generate Gray Code bytes; i.e. values in range from 0 to 255.
DEFINT A-Z
FOR X=0 TO 255
        GRAY = X XOR (INT(X/2))
        rem Print or output the Gray Code value in GRAY.
NEXT X