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.

Floris · Accepted Answer · 2014-01-10T00:59:05.480

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.

Yup, XORing with a zero does nothing, result bit is unchanged. XORing with a 1 always toggles the bit. — Graeme, Jan 10 '14 at 00:37
yeah I guess, I feel like I will never realize when to use it though. — AyBayBay, Jan 10 '14 at 00:38
@AyBayBay You will if you get more experience and work on a broader class of problems. It's a rather infrequent operation, so don't be concerned if you haven't encountered a need for it. — Jim Balter, Jan 10 '14 at 00:57
yeah I am just nervous I have a programming test with a networking company tomorrow, they said it will be all C so I am concerned it will be low-level bit operations. Most of my school work has been higher level challenges so I do not have much experience in this. At this point I am trying to memorize certain cases in which to apply these operations — AyBayBay, Jan 10 '14 at 01:00
Good luck in the interview! I just thought of another (very practical) use of XOR - it is used in the FFT algorithm. See for example http://hackage.haskell.org/package/feldspar-language-0.6.0.3/docs/src/Feldspar-Algorithm-FFT.html or (in C) http://www.katjaas.nl/FFTimplement/FFTimplement2.html — Floris, Jan 10 '14 at 01:04
XOR is used extensively in cryptography. as a matter of fact a simple XOR cypher is unbreakable if the key is truly random and as long as the plaintext. — Norill Tempest, Dec 25 '22 at 20:50
@NorillTempest - but if I'm not mistaken, such a key cannot be communicated, which makes it OK for cryptography but not for encrypting communication. It's perfect for "shared secret" - each team member gets an apparently random file, and only the XOR of all the files makes sense. Great for making sure "all the kids show up for the reading of the will"... — Floris, Jan 04 '23 at 23:10

haccks · Answer 2 · 2014-01-10T01:00:50.547

3

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)); 
}

edited Jan 10 '14 at 01:00

answered Jan 10 '14 at 00:46

haccks

104,019
25
176
264

1

Never seen that one, that's sexy! – Keeler Jan 10 '14 at 00:54
Wouldn't the (x < y) part be compiled using conditional branches? – mcleod_ideafix Jan 10 '14 at 01:00
@Floris; What I mean to say is without using `if`. Corrected now. – haccks Jan 10 '14 at 01:01
It's cool. Is this faster than `#define MAX(a,b) ((a)>(b))?(a):(b)` ? – Floris Jan 10 '14 at 01:01
1

@Floris; Sorry. I have no idea about this. This an interview question asked in a campus placement. (Let me think about this). – haccks Jan 10 '14 at 01:05

mcleod_ideafix · Answer 3 · 2014-01-10T01:31:55.807

On the creative side, the XOR operation is usually employed to render simple square graphics based upon current X and Y coordinates of a given point. For example, a chess board look alike pattern with variable cell size:

#include <stdio.h>

#define CELLSIZE 2   /* cell size is actually 2 power CELLSIZE */
#define MASK (1<<CELLSIZE)

int main()
{
    int i,j;

    for (i=0;i<32;i++)
    {
        for (j=0;j<32;j++)
            putchar (' '+('*'-' ')*( ((i&MASK)^(j&MASK))!=0 ) );
        putchar ('\n');
    }
    return 0;
}

    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****

In videogame coding, when you don't have hardware sprites and/or multiple playfields, the simplest way to draw a sprite on the top of a bitmapped background so you can erase it at your convenience without having to store the part of screen the sprite modifies, is to XOR the sprite pixels with background pixels (one pixel is encoded by one bit). To erase the sprite, simply draw it again at the same coordinates. This method can also be seen to render the mouse pointer on some non accelerated display hardware.

Keeler · Answer 4 · 2014-01-10T01:51:28.297

2

One of my favorite examples is an in-place swap. (Note: this is C++ code, not C code, but you get the idea.)

void swap(int &x, int &y)
{
    x ^= y;
    y ^= x;
    x ^= y;
}

You can also toggle single bits: (n is the nth bit, which gets toggled in b)

a = b ^ (1 << n)

Another, less common use: XOR Linked Lists:

You can hold onto the XOR of the next and previous items instead of holding onto a pointer for each. These days, we have so much memory that it probably doesn't matter, but hey, it's still kind of cool. (Unless you're on an embedded system and you need a doubly-linked list for some reason. Then you'll be happy you read this.)

edited Jan 10 '14 at 01:51

answered Jan 10 '14 at 00:38

Keeler

2,102
14
20

Using bitwise xor to swap two numbers is *clever* -- and in this case that's a bad thing. For one thing, it fails if `x` and `y` point to the same object. Just use a temporary. If the objects being swapped are very large and you can't afford to allocate a temporary, use a loop to swap a byte or word at a time. – Keith Thompson Jan 10 '14 at 01:23
As for the xor linked list trick, that's equally *clever*. It leave the list in an inconsistent state as you're traversing it, and this kind of bit manipulation on pointers is, strictly speaking undefined behavior (though you're likely to get away with it on *most* systems). – Keith Thompson Jan 10 '14 at 01:24
1

`x` and `y` cannot point to the same object, they are both integers. Unless you call it as `swap(x, x)`, which does nothing. :) – Keeler Jan 10 '14 at 01:25
Agreed about using xor on pointers, though. That's actually terrifying, now that I think about it. However, it's just an interesting thing you can do, like most of the other examples here. – Keeler Jan 10 '14 at 01:28
My mistake: `x` and `y` aren't pointers, they're syntax errors. (The question is tagged C, not C++.) – Keith Thompson Jan 10 '14 at 01:40
True! Even the question title says C. Oops! Well, y'all get the idea. – Keeler Jan 10 '14 at 01:50

score 0 · Answer 5 · answered Dec 18 '16 at 06:00

An application of XOR can be seen in particular when an array with every number being repeated except one is given and the non-repeated single number is to be found. Taking XOR of all the numbers would result the number which occurred only once.

int arr[]={1, 1, 2, 2, 3, 3, 4};
// frequency of every number in the array is 2 except one number.
int sz=7; //size of array
int x=0; 
for(int i=0;i<sz;i++)
   x^=arr[i];
// x would give the number 4 here

XOR operator in C

5 Answers5

Linked