Practical uses of XOR

C

cman

Could you point me to the practical uses of XOR in assembly and
algorithms? I understand XOR to be "true if and only if p is true or q
is true". Where is this used? I draw a blank on usage.

Tilak
 
M

Mark McIntyre

Could you point me to the practical uses of XOR in assembly and
algorithms? I understand XOR to be "true if and only if p is true or q
is true". Where is this used? I draw a blank on usage.

This isn't a C question. Ask again in comp.programming or a maybe
maths group, and in the meantime, think about how two-way light
switches work, like the ones in the stairwell of most houses.
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan
 
R

Richard Bos

cman said:
Could you point me to the practical uses of XOR in assembly and
algorithms? I understand XOR to be "true if and only if p is true or q
is true". Where is this used? I draw a blank on usage.

The very simplest of applications: to invert a B&W bitmap image, xor
each byte with ~0.
For more involved examples, one uses ^ in conjunction (NPI) with & and |
for reading, setting, and toggling flags within bytes.

Richard
 
S

santosh

cman said:
Could you point me to the practical uses of XOR in assembly and
algorithms? I understand XOR to be "true if and only if p is true or q
is true". Where is this used? I draw a blank on usage.

Tilak

Don't post all your questions to comp.lang.c. This group only deals
with ISO C. Post non-C questions to appropriate groups. For this one,
comp.programming, alt.lang.asm, comp.lang.asm.x86, or sci.math might
be better candidates. The web is also a good resource for such simple
questions.

<http://en.wikipedia.org/wiki/XOR>
 
K

Keith Thompson

The very simplest of applications: to invert a B&W bitmap image, xor
each byte with ~0.
[...]

Surely it's simpler to invert the image itself, using the unary "~"
operator, rather than constructing another bitmap and xor'ing against
that.
 
R

Roberto Waltman

Richard said:
The very simplest of applications: to invert a B&W bitmap image, xor
each byte with ~0.

Too complicated ...

#include <stdio.h>
extern delay_until_next_second(void);

void clock_simulator(void)
{
int sound = 0;
while (1)
{
printf(sound ? "Tick\n" : "Tock\n");
delay_until_next_second();
sound ^= 1;
}
}
 
C

CBFalconer

santosh said:
Don't post all your questions to comp.lang.c. This group only deals
with ISO C. Post non-C questions to appropriate groups. For this one,
comp.programming, alt.lang.asm, comp.lang.asm.x86, or sci.math might
be better candidates. The web is also a good resource for such simple
questions.

However C has an XOR operator, spelled '^'. The OP should just
read his C book.
 
K

Keith Thompson

Roberto Waltman said:
Too complicated ...

#include <stdio.h>
extern delay_until_next_second(void);

void clock_simulator(void)
{
int sound = 0;
while (1)
{
printf(sound ? "Tick\n" : "Tock\n");
delay_until_next_second();
sound ^= 1;
}
}

Simpler:

sound = 1 - sound;

Even simpler:

sound = !sound;
 
B

Ben Pfaff

Keith Thompson said:
Simpler:

sound = 1 - sound;

Even simpler:

sound = !sound;

I'd probably write it like this (modulo coding style):

void clock_simulator(void)
{
while (1)
{
printf("Tock\n");
delay_until_next_second();

printf("Tick\n");
delay_until_next_second();
}
}
 
G

Guest

Too complicated ...

#include <stdio.h>
extern delay_until_next_second(void);

void clock_simulator(void)
{
int sound = 0;
while (1)
{
printf(sound ? "Tick\n" : "Tock\n");
delay_until_next_second();
sound ^= 1;

Why an exclusive or with 1? Why not 8, or 42, or 197? And why not
simply

sound = !sound;

? This doesn't seem to me an obvious use of xor... which could just be
me, of course.
 
B

Beej Jorgensen

Keith Thompson said:
Surely it's simpler to invert the image itself, using the unary "~"
operator, rather than constructing another bitmap and xor'ing against
that.

<OT>
Yes, but probably what he was getting at was more along the lines of the
famous Atari (was it?) XOR patent for drawing the cursor, namely, that
you can "stamp" arbitrary data on other data, and remove it again with
XOR, since:

(x ^ y) ^ y == x

(I'm sure you already knew this, Keith; this post is for posterity.)

Cursor on:

....XXX.. XXXXXXXX XXX...XX
...XX.XX. XXXXXXXX XX..X..X
..XX...XX XXXXXXXX X..XXX..
..XXXXXXX XXXXXXXX X.......
..XX...XX XOR XXXXXXXX == X..XXX..
..XX...XX XXXXXXXX X..XXX..
..XX...XX XXXXXXXX X..XXX..
......... XXXXXXXX XXXXXXXX

Then cursor off:

XXX...XX XXXXXXXX ...XXX..
XX..X..X XXXXXXXX ..XX.XX.
X..XXX.. XXXXXXXX .XX...XX
X....... XXXXXXXX .XXXXXXX
X..XXX.. XOR XXXXXXXX == .XX...XX
X..XXX.. XXXXXXXX .XX...XX
X..XXX.. XXXXXXXX .XX...XX
XXXXXXXX XXXXXXXX ........

Of course, the cursor could be anything--not just a solid block--and the
character beneath would be restored to its original state when the
cursor was turned off.

IIRC, old versions of Windows would draw the window frame in XOR mode
when you were moving or resizing it. Ugly but effective.

</OT>

-Beej, still looking for that elusive XNOT operation.
 
P

pete

Simpler:

sound = 1 - sound;

Even simpler:

sound = !sound;

That's less typing,
but I consider a logical operation on a variable
to be more complicated
than an arithmetic operation between a variable and a constant.
 
W

Walter Roberson

Could you point me to the practical uses of XOR in assembly and
algorithms? I understand XOR to be "true if and only if p is true or q
is true". Where is this used? I draw a blank on usage.

Suppose you are trying to detect a zero crossing in a list of
values. There is a crossing if one value is less than zero and
the other is greater than zero. You could code something
such as:

(x < 0 && y > 0) || (x > 0 && y < 0)

or you could use the shorter

(x < 0) ^ (y < 0)

(Note: the two forms are not exactly equivilent if one of the values
is exactly 0; you need more data samples to decide zero crossings
if the values can be exactly 0.)
 
G

Guest

Walter said:
Suppose you are trying to detect a zero crossing in a list of
values. There is a crossing if one value is less than zero and
the other is greater than zero. You could code something
such as:

(x < 0 && y > 0) || (x > 0 && y < 0)

or you could use the shorter

(x < 0) ^ (y < 0)

This too does not seem like an obvious use of xor to me.

(x < 0) != (y < 0)
 
R

Roberto Waltman

Keith Thompson said:
...
Even simpler:
sound = !sound;

Agreed, and that is what I would use if I needed something to cycle
between two states. But it would not qualify as an xor usage example,
would it?

Roberto Waltman

[ Please reply to the group,
return address is invalid ]
 
K

Keith Thompson

Roberto Waltman said:
Agreed, and that is what I would use if I needed something to cycle
between two states. But it would not qualify as an xor usage example,
would it?

No, it wouldn't. My point is that, given the existence of a simpler
and clearer method of doing the same thing, "sound ^= 1;' doesn't
qualify as a *practical* use of xor. With enough work, you can
replace many, perhaps most, perhaps even all, C operators with xor;
that doesn't mean it's a good idea to do so.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,906
Latest member
SkinfixSkintag

Latest Threads

Top