XOR bug

I wanted to share an intriguing bug today.

I was trying out insertion and selection sort. Here is the code :

#include <iostream>
using namespace std;

void selectionSort(int nos[], int len){

//    int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};

for(int i=0;i<len;i++){

    int min_value = 0x7fffffff;
    int index_of_min_value;
 
    for(int j=i;j<len;j++){
         if(nos[j] < min_value){
            min_value = nos[j];
            index_of_min_value = j;
        }
    }

                    int temp = nos[i];
                    nos[i] = min_value;
                    nos[index_of_min_value] = temp;     
       
          }

}

void insertionSort(int nos[], int len){
     
    for(int i=1;i<len;i++){
          for(int j=i;j>0;j--){
                    if(nos[j] > nos[j-1]){
                              break;
                    }
         
                    int temp = nos[j-1];
                    nos[j-1] = nos[j];
                    nos[j] = temp;       
        }   
    }
}

void printElementsOfArray(int nos[], int len){
    for(int i=0;i<len;i++)
        cout << nos[i] << endl;
 
     cout << endl;
}

int main()
{

    int nos1[] = {24, 13, 9, 64, 7, 23, 34, 47};
    int nos2[] = {24, 13, 9, 64, 7, 23, 34, 47};
 
 
    int len = sizeof(nos1)/sizeof(int);
 
    insertionSort(nos1, len);
    printElementsOfArray(nos1, len);


    selectionSort(nos2, len);
    printElementsOfArray(nos2, len);
 

 
   return 0;
}

I got the input as expected.

7
9
13
23
24
34
47
64

7
9
13
23
24
34
47
64

But, now i wanted to try out xor swaps instead of temporary variable swaps. (something that i learnt recently : =) ) Below is the updated code for selection sort.

void selectionSort(int nos[], int len){

//    int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};

for(int i=0;i<len;i++){

    int min_value = 0x7fffffff;
    int index_of_min_value;

    for(int j=i;j<len;j++){
         if(nos[j] < min_value){
            min_value = nos[j];
            index_of_min_value = j;
        }
    }

       
          nos[i] ^= nos[index_of_min_value];
          nos[index_of_min_value] ^= nos[i];
          nos[i] ^= nos[index_of_min_value];

          }

}

Now the output

7
9
13
23
24
34
47
64

7
9
0
23
0
34
47
0

Hmm...interesting! I was puzzled. I knew that was the right code for swapping but what's that.

I printed out the array state after each swap in selection sort.

#include <iostream>

using namespace std;

void printElementsOfArray(int nos[], int len){
 
    for(int i=0;i<len;i++)
        cout << nos[i] << " ";
 
    cout << endl;

}


void selectionSort(int nos[], int len){


//    int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};


for(int i=0;i<len;i++){
 
 
    int min_value = 0x7fffffff;
    int index_of_min_value;
 
    for(int j=i;j<len;j++){
             
        if(nos[j] < min_value){
            min_value = nos[j];
            index_of_min_value = j;
        }
             
    }
 
          nos[i] ^= nos[index_of_min_value];
          nos[index_of_min_value] ^= nos[i];
          nos[i] ^= nos[index_of_min_value];
         
           printElementsOfArray(nos, len);

     
}
}


int main()
{
 
    int nos1[] = {24, 13, 9, 64, 7, 23, 34, 47};
    int nos2[] = {24, 13, 9, 64, 7, 23, 34, 47};
 
 
    int len = sizeof(nos1)/sizeof(int);
 
    insertionSort(nos1, len);

  //  printElementsOfArray(nos1, len);

    selectionSort(nos2, len);
 
//    printElementsOfArray(nos2, len);
 
   return 0;
}


I get the output


//    int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};

7 13 9 64 24 23 34 47  ->step 1
7 9 13 64 24 23 34 47  ->step 2
7 9 0 64 24 23 34 47    ->step 3
7 9 0 23 24 64 34 47
7 9 0 23 0 64 34 47
7 9 0 23 0 34 64 47
7 9 0 23 0 34 47 64
7 9 0 23 0 34 47 0
    
In step 3,  we know the problem. XOR swap works on two separate variables but in step 3 we are swapping it with itself. In other words we are doing a^a three times which will always be 0.

Ahh.. The lesson , If you want to use xor swaps, make sure you are not swapping the same place.

Here was a quick fix.

void selectionSort(int nos[], int len){


//    int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};


for(int i=0;i<len;i++){
 
    int min_value = 0x7fffffff;
    int index_of_min_value;
 
    for(int j=i;j<len;j++){
             
        if(nos[j] < min_value){
            min_value = nos[j];
            index_of_min_value = j;
        }
             
    }
         
            if( i  != index_of_min_value){  
                    nos[i] ^= nos[index_of_min_value];
                    nos[index_of_min_value] ^= nos[i];
                    nos[i] ^= nos[index_of_min_value];
            }
                 
}
   
}