Practical uses of XOR

[Richard Bos]

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

If that's all you're doing, yes. Often one uses a generic bitblt-like
facility to XOR the entire bitmap with a pattern, or another bitmap, of
one's choice. These facilities are usually heavily optimised, possibly
even more so than a hand-rolled loop to invert all bytes can be. In that
case, one would use the xor-bitblt-like with a 1-filled pattern to
invert it. And that would be the simplest use of XOR, though not the
simplest (but sometimes the most efficient) way to invert a bitmap.

Richard

 

[Marcin Wolcendorf]

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

Can be used to exchange values of two integers of the same size:
a ^= b;
b ^= a;
a ^= b;

M.

 

[Richard Heathfield]

Marcin Wolcendorf said:

Can be used to exchange values of two integers of the same size:
a ^= b;
b ^= a;
a ^= b;

I haven't seen the original yet, so this reply is half a piggyback. But
before I get onto that, can I just say that this exchange thingy is not
a great use of XOR? For one thing, it only works with integers. For
another, it's not very clear. For a third, it's hard to optimise. And
for a fourth, it breaks if you have pointers to integer, use *a ^= *b
etc, and a and b point to the same integer!

Now to get back to the OP.

XOR yields true if its operands differ. So:

A B A XOR B
F F F
F T T
T F T
T T F

It is often used in cryptography, because it has the useful property
that if C = P XOR K, then P = C XOR K.

Look up, for example, "one time pad" or "Feistel Network".

 

[Marcin Wolcendorf]

Marcin Wolcendorf said:


I haven't seen the original yet, so this reply is half a piggyback. But
before I get onto that, can I just say that this exchange thingy is not
a great use of XOR? For one thing, it only works with integers.

Well, true- I'd rather not use it with floats...

For
another, it's not very clear.

This is your opinion. The author did't ask for _clear_ things but for
practical.

For a third, it's hard to optimise.

a = b; is equally hard to optimise. What is your point?

And
for a fourth, it breaks if you have pointers to integer, use *a ^= *b
etc, and a and b point to the same integer!

You're sure of that? Checked that? Then run this:
#include <stdio.h>
#include <stdlib.h>

main()
{
unsigned a = 10;
unsigned b = 20;
unsigned *c = &a;
unsigned *d = &b;

*c ^= *d;
*d ^= *c;
*c ^= *d;

printf("a= %d, b= %d\n", a, b);
}
and say with straight face, that you didn't get
a= 20, b= 10

M.

 

[Richard Heathfield]

Marcin Wolcendorf said:

Marcin Wolcendorf said:
[...xor...]

Can be used to exchange values of two integers of the same size:
a ^= b;
b ^= a;
a ^= b;

I haven't seen the original yet, so this reply is half a piggyback.
But before I get onto that, can I just say that this exchange thingy
is not a great use of XOR? For one thing, it only works with
integers.

Well, true- I'd rather not use it with floats...

Indeed. But then, I'd rather not use it with ints either.

This is your opinion. The author did't ask for _clear_ things but for
practical.

Code you can't read is code you can't fix. Code you can't fix is not
practical code.

a = b; is equally hard to optimise. What is your point?

Actually a = b; can be very simple to optimise. For example, if the
compiler knows that the two values are already the same, as it may well
do in some situations, it can omit the assignment completely. But the
compiler will have a much harder job guessing what you're up to with
the three-statement-XOR thing, and so it will be more reluctant to
optimise.

You're sure of that?
Yes.

Checked that?
Yes.

Then run this:
#include <stdio.h>
#include <stdlib.h>

main()
{
unsigned a = 10;
unsigned b = 20;
unsigned *c = &a;
unsigned *d = &b;

*c ^= *d;
*d ^= *c;
*c ^= *d;

printf("a= %d, b= %d\n", a, b);
}
and say with straight face, that you didn't get
a= 20, b= 10

Your program does not illustrate my objection.

Run this instead:

#include <stdio.h>

int main(void)
{
unsigned a = 10;
unsigned *c = &a;
unsigned *d = &a;
*c ^= *d;
*d ^= *c;
*c ^= *d;
printf("a = %u\n", a);
return 0;
}

and tell me with a straight face that you got 10.

 

[Army1987]

Marcin Wolcendorf said:

Can be used to exchange values of two integers of the same size:
a ^= b;
b ^= a;
a ^= b;

I haven't seen the original yet, so this reply is half a piggyback. But
before I get onto that, can I just say that this exchange thingy is not
a great use of XOR? For one thing, it only works with integers. [snip]
And
for a fourth, it breaks if you have pointers to integer, use *a ^= *b
etc, and a and b point to the same integer!

Re-read the line above...

You're sure of that? Checked that? Then run this:
#include <stdio.h>
#include <stdlib.h>

main()
{
unsigned a = 10;
unsigned b = 20;
unsigned *c = &a;
unsigned *d = &b;

c and d don't point to the same integer.

 

[CBFalconer]

Can be used to exchange values of two integers of the same size:
a ^= b;
b ^= a;
a ^= b;

Don't use it. See what happens when &a == &b, or when the
variables cannot be handled by xor operations.

 

[David Starr]

Can be used to exchange values of two integers of the same size:
a ^= b;
b ^= a;
a ^= b;

M.

XOR is useful to toggle a single bit in a flagword. If you want the
state of the bit changed (a one goes to a zero, or a zero goes to a
one) XOR a bitmask with the flag word.
For instance.

int flagword;
# define TOGGLE_BIT 4

flagword ^= TOGGLE_BIT;

Bit 2 will now be in the opposite state, if it used to be a one it will
be a zero. If it used to be a zero it will be a one. This action is
occasionally useful, although it's not something I do every day.
Or, support I have two like devices with status indicated by a set of
bits in a control word. And I wish to see if both devices are in the
same state.

int device_a, device_b;
int sameness;

sameness = device_a ^ device_b;

if (sameness == 0)
/* devices are in the same state */
else
/* something is different. One bits in sameness will
tell which bits differ between device_a & device_b */


David Starr





David Starr

 

[pete]

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.

/*
** (size ^ size - 1) isolates the lowest set significant bit
** of (size), when (size) is equal to the sizeof one array member.
*/

void *losearch(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
int comp;
size_t odd_mask, bytes, middle, high, low;
const unsigned char *array, *found;

found = NULL;
if (nmemb != 0) {
odd_mask = size ^ size - 1;
array = base;
low = 0;
high = nmemb * size;
do {
bytes = high - low;
middle = (bytes & odd_mask ? bytes - size : bytes) / 2
+ low;
base = middle + array;
comp = compar(key, base);
if (comp > 0) {
low = middle;
} else {
high = middle;
if (comp == 0) {
found = base;
}
}
} while (bytes != size);
}
return (void *)found;
}

 

[Giorgos Keramidas]

Can be used to exchange values of two integers of the same size:
a ^= b;
b ^= a;
a ^= b;

It can be used to amaze fellow students with a smart XOR-based solution
to the problem:

"We have a list of all the integer numbers from 0 up to the k-th power
of two, except for one of the numbers. Write a program to find the
missing integer."

Other than that, it's just another useful bitwise operation

- Giorgos

 

[Charles Richmond]

Can be used to exchange values of two integers of the same size:
a ^= b;
b ^= a;
a ^= b;

In monochrome graphics, exclusive "or" with screen memory
is used to put an image on the screen, then erase it, then
place the image at another position.

 

[Default User]

Marcin Wolcendorf said:


I haven't seen the original yet, so this reply is half a piggyback.

I think you have. The original was posted on March 12.




Brian

 

[Richard Heathfield]

Default User said:

Richard Heathfield wrote:


I think you have. The original was posted on March 12.

Oh, okay - I believe you, obviously. My Usenet memory is good for
short-term, and not too bad for (important) long-term, but six weeks?
No chance.

 

[Default User]

Default User said:


Oh, okay - I believe you, obviously. My Usenet memory is good for
short-term, and not too bad for (important) long-term, but six weeks?
No chance.

Well, I recognized that it was an old message, and looked it up on
Google Groups to get the exact date.





Brian

 

[Joe Wright]

Default User said:


Oh, okay - I believe you, obviously. My Usenet memory is good for
short-term, and not too bad for (important) long-term, but six weeks?
No chance.

They say memory is the second thing to go. I forget what the first thing
is.

Ronald Reagan in later years opined that one of the good things about
Alzheimer's was that you get to meet so many new people every day.

 

[BiGYaN]

I got :
a=20, b=10

But then that's exactly what the program is supposed to do.

Am I missing something here?

 

[Ian Collins]

I got :
a=20, b=10

But then that's exactly what the program is supposed to do.

Am I missing something here?

Context?

 

[Keith Thompson]

I got :
a=20, b=10

But then that's exactly what the program is supposed to do.

Am I missing something here?

Yes, context. You need to quote enough of the parent article so your
followup makes sense to someone who hasn't seen the parent. You're
posting through groups.google.com, which does this for you
automatically.