446,227 Members | 1,315 Online
Need help? Post your question and get tips & solutions from a community of 446,227 IT Pros & Developers. It's quick & easy.

# Practical uses of XOR

 P: n/a 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 Mar 12 '07 #1
37 Replies

 P: n/a On 12 Mar 2007 09:14:29 -0700, in comp.lang.c , "cman" Could you point me to the practical uses of XOR in assembly andalgorithms? I understand XOR to be "true if and only if p is true or qis 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 Mar 12 '07 #2

 P: n/a "cman"

 P: n/a "cman" writes: 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 XOR is fundamental to cryptographic work. It is also used in binary arithmetic. http://en.wikipedia.org/wiki/Adder_(electronics) Mar 12 '07 #4

 P: n/a cman wrote: 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. Mar 12 '07 #5

 P: n/a On Mar 12, 9:14 am, "cman"

 P: n/a rl*@hoekstra-uitgeverij.nl (Richard Bos) writes: "cman" Could you point me to the practical uses of XOR in assembly andalgorithms? I understand XOR to be "true if and only if p is true or qis 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. [...] Surely it's simpler to invert the image itself, using the unary "~" operator, rather than constructing another bitmap and xor'ing against that. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <* "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister" Mar 12 '07 #7

 P: n/a Richard Bos wrote: >"cman" Could you point me to the practical uses of XOR in assembly andalgorithms? I understand XOR to be "true if and only if p is true or qis true". Where is this used? I draw a blank on usage. The very simplest of applications: to invert a B&W bitmap image, xoreach byte with ~0. Too complicated ... #include 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; } } Mar 12 '07 #8

 P: n/a santosh wrote: cman wrote: >Could you point me to the practical uses of XOR in assembly andalgorithms? I understand XOR to be "true if and only if p is trueor q is true". Where is this used? I draw a blank on usage. 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. -- Chuck F (cbfalconer at maineline dot net) Available for consulting/temporary embedded and systems. -- Posted via a free Usenet account from http://www.teranews.com Mar 12 '07 #9

 P: n/a Roberto Waltman >"cman" >Could you point me to the practical uses of XOR in assembly andalgorithms? I understand XOR to be "true if and only if p is true or qis true". Where is this used? I draw a blank on usage. The very simplest of applications: to invert a B&W bitmap image, xoreach byte with ~0. Too complicated ... #include 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; -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <* "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister" Mar 12 '07 #10

 P: n/a Keith Thompson #include 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; 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(); } } -- int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\ \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\ );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\ );}return 0;} Mar 12 '07 #11

 P: n/a On Mar 12, 9:31 pm, Roberto Waltman 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. } } Mar 12 '07 #12

 P: n/a Keith Thompson Surely it's simpler to invert the image itself, using the unary "~"operator, rather than constructing another bitmap and xor'ing againstthat. 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. -Beej, still looking for that elusive XNOT operation. Mar 12 '07 #13

 P: n/a On Mar 12, 11:14 am, "cman"

 P: n/a Op Tue, 13 Mar 2007 00:21:51 +0100 (CET) schreef Beej Jorgensen: -Beej, still looking for that elusive XNOT operation. -- Coos Mar 13 '07 #15

 P: n/a Keith Thompson wrote: > Roberto Waltman The very simplest of applications: to invert a B&W bitmap image, xoreach byte with ~0. Too complicated ... sound ^= 1; > 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. -- pete Mar 13 '07 #16

 P: n/a In article <11**********************@t69g2000cwt.googlegroups .com>, cman Could you point me to the practical uses of XOR in assembly andalgorithms? I understand XOR to be "true if and only if p is true or qis 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.) -- Is there any thing whereof it may be said, See, this is new? It hath been already of old time, which was before us. -- Ecclesiastes Mar 13 '07 #17

 P: n/a Walter Roberson wrote: In article <11**********************@t69g2000cwt.googlegroups .com>, cman

 P: n/a Keith Thompson ...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 ] Mar 13 '07 #19

 P: n/a Roberto Waltman >...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? 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. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <* "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister" Mar 13 '07 #20

 P: n/a Keith Thompson

 P: n/a cman

 P: n/a Marcin Wolcendorf said: cman Could you point me to the practical uses of XOR in assembly andalgorithms? I understand XOR to be "true if and only if p is true orq 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; 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". -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Apr 25 '07 #23

 P: n/a Richard Heathfield cman >Could you point me to the practical uses of XOR in assembly andalgorithms? I understand XOR to be "true if and only if p is true orq 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; 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 #include 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. Apr 25 '07 #24

 P: n/a Marcin Wolcendorf said: Richard Heathfield 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 thingyis not a great use of XOR? For one thing, it only works withintegers. Well, true- I'd rather not use it with floats... Indeed. But then, I'd rather not use it with ints either. > >Foranother, it's not very clear. 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. > >For a third, it's hard to optimise. 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. >Andfor a fourth, it breaks if you have pointers to integer, use *a ^= *betc, and a and b point to the same integer! You're sure of that? Yes. Checked that? Yes. Then run this: #include #include 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 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. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Apr 25 '07 #25

 P: n/a "Marcin Wolcendorf" 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. Butbefore I get onto that, can I just say that this exchange thingy is nota great use of XOR? For one thing, it only works with integers. [snip] >Andfor a fourth, it breaks if you have pointers to integer, use *a ^= *betc, 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 #include main() { unsigned a = 10; unsigned b = 20; unsigned *c = &a; unsigned *d = &b; c and d don't point to the same integer. *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 Apr 25 '07 #26

 P: n/a Marcin Wolcendorf wrote: cman Could you point me to the practical uses of XOR in assembly andalgorithms? I understand XOR to be "true if and only if p is true or qis 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. 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 Apr 25 '07 #27

 P: n/a Marcin Wolcendorf wrote: cman Could you point me to the practical uses of XOR in assembly andalgorithms? I understand XOR to be "true if and only if p is trueor q is true". Where is this used? I draw a blank on usage. 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. -- cbfalconer at maineline.net -- Posted via a free Usenet account from http://www.teranews.com Apr 25 '07 #28

 P: n/a cman wrote: > 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; } -- pete Apr 25 '07 #29

 P: n/a Marcin Wolcendorf cman Could you point me to the practical uses of XOR in assembly andalgorithms? I understand XOR to be "true if and only if p is true or qis true". Where is this used? I draw a blank on usage. 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 Apr 25 '07 #30

 P: n/a Marcin Wolcendorf wrote: cman Could you point me to the practical uses of XOR in assembly andalgorithms? I understand XOR to be "true if and only if p is true or qis 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; 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. -- +----------------------------------------------------------------+ | Charles and Francis Richmond richmond at plano dot net | +----------------------------------------------------------------+ Apr 25 '07 #31

 P: n/a Richard Heathfield wrote: Marcin Wolcendorf said: cman 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; 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 Apr 25 '07 #32

 P: n/a Default User said: Richard Heathfield wrote: >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. 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. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Apr 25 '07 #33

 P: n/a Richard Heathfield wrote: Default User said: Richard Heathfield wrote: 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. 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 Apr 25 '07 #34

 P: n/a Richard Heathfield wrote: Default User said: >Richard Heathfield wrote: >>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. 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. -- Joe Wright "Everything should be made as simple as possible, but not simpler." --- Albert Einstein --- Apr 25 '07 #35

 P: n/a I got : a=20, b=10 But then that's exactly what the program is supposed to do. Am I missing something here? Apr 26 '07 #36

 P: n/a BiGYaN wrote: I got : a=20, b=10 But then that's exactly what the program is supposed to do. Am I missing something here? Context? -- Ian Collins. Apr 26 '07 #37

 P: n/a BiGYaN San Diego Supercomputer Center <* "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister" Apr 26 '07 #38

### This discussion thread is closed

Replies have been disabled for this discussion.