XOR operator in C

Question

I am having some trouble identifying when to use the XOR operator when doing bitwise manipulations. Bitwise And and Or are pretty straight forward. When you want to mask bits, use a bitwise AND (common use case is IP Addressing and subnet masks). When you want to turn bits on use the inclusive or. However, the XOR always gets me and I feel like if asked a question in an interview that requires using XOR I will never get it. Can someone shed some light on when to use it and some common use cases.

Answer 1

You use exclusive or to flip bits - the ones that are ON are turned OFF, and vice versa. This can be handy for swapping two numbers without having space for a third number, for example.

0x0A ^ 0xFF = 0x03 ( 00001010 ^ 11111111 = 11110101 )

Swapping numbers:

operation   example 
             A      B
initial:   0011    1010
a = a^b;   1001    1010
b = a^b;   1001    0011
a = a^b;   1010    0011

As you can see, the numbers (nibbles in this case) A and B were swapped without using additional space. This works for any two numbers of the same type (although in C, bitwise operators expect unsigned integers)

XOR operations are also used for "weak encryption". You can take the XOR of a string with a (repeated) "code word", and the result will be a string of bytes that make no sense. Apply the same operation again, and the original appears. This is quite a weak algorithm, and should never be used in real life.

Regarding toggling bits - in the "olden days", if you wanted to invert an image, you would do pix = pix & 1 for each pixel - or if you could do it a byte at a time, byte = byte & 0xFF. This would turn black text on a white background into white text on a black background. I think ATARI had a patent for creating a blinking cursor "anywhere on the screen" by doing XOR with the bit map.

Similarly if you have a microcontroller that wants to create a blinking light, repeatedly doing state = state XOR 1 will cause the state to toggle.

Finallly, there are many "bit twiddling hacks" that rely on the XOR operation. For example, computing the parity of a word (i.e. whether the number of set bits is odd or even) can be done with the following (source: http://graphics.stanford.edu/~seander/bithacks.html)

unsigned int v;  // word value to compute the parity of
v ^= v >> 16;
v ^= v >> 8;
v ^= v >> 4;
v &= 0xf;
return (0x6996 >> v) & 1;

There are many other "clever tricks" - they usually show up when you are trying to find the fastest way to do something that involves bit manipulation. Most people can go through life perfectly fine without ever really "getting" it, and that's OK. Me, I like bit fiddling.

Answer 2

Beside of the swapping of two numbers and bits toggling as other answers explains bit-wise XOR is also used in finding the maximum of two numbers without using if statement

int max(int x, int y)
{
      return x ^ ((x ^ y) & -(x < y)); 
}