Pointer issue when applying the XOR swap algorithm

Question

I have an array of floats where I want to do some swapping. So, I looked around on the net and I found out that the most efficient way of doing it is through XOR swapping XOR swap algorithm

So I have this code snippet:

  float tmp;
  tmp   = x[i];
  x[i]  = x[j];
  x[j]  = tmp;

And I've tried to change it to the XOR swap way:

  /*Made sure that address x[i] is different than the one of x[j] */
  float* a= &x[i];
  float* b= &x[j];
  a ^= b;
  b ^= a;
  a ^= b;

But I get this : error: invalid operands to binary ^ (have ‘float *’ and ‘float *’).

Honestly, I'm not such an expert with pointers and sometimes it confuses me, So, can someone tell me what I'm doing wrong.

`float* a= x[i]; float* b= x[j];` are actually constaint violation, IIRC. — Sourav Ghosh, Jul 11 '17 at 14:28
`a ^= b;` is invalid. You cannot possibly use XOR on pointers and even if you could, it'd be meaningless. — Sourav Ghosh, Jul 11 '17 at 14:31
What is not clear in the error message? Bitwise operations are defined for integer types only. — Eugene Sh., Jul 11 '17 at 14:31
@A.nechi First of all it is in general a bad idea to use the XOR operator for swapping and moreover trying to use it for float numbers.:) — Vlad from Moscow, Jul 11 '17 at 14:31
@VladfromMoscow On *pointers* to float numbers - is even a worse idea... — Eugene Sh., Jul 11 '17 at 14:32
Why do you think it is efficient? Usually, a regular swap with a temp variable is faster. — klutt, Jul 11 '17 at 14:40
Actually XOR swapping is the exception to the rule that XOR on pointers is meaningless. You can also use AND and OR at a low level to force pointer alignment, though you have to fool the C compiler. — Malcolm McLean, Jul 11 '17 at 14:41
@klutt It *can* be more efficient. One can claim it is using less memory. But it is micro-optimization, and an arguable one. — Eugene Sh., Jul 11 '17 at 14:41
I thought that the Xor swap uses fewer registers ... The method that I'm posting uses a lot of registers ... Or does the compiler handles this process?? — A.nechi, Jul 11 '17 at 14:42
I suggest you read the entire Wikipedia XOR swap page that you linked to, particularly [this section](https://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_use_in_practice). — Paul R, Jul 11 '17 at 14:45
Don't do premature optimisations. Leave this to the compiler in the first place. If your code is indeed not fast enough, profile to identify hotspots and optimise those using common patterns the compiler will recognise. — too honest for this site, Jul 11 '17 at 14:48
From the link you posted, _Most modern compilers can optimize away the temporary variable in the native swap, in which case ***the native swap uses the same amount of memory and the same number of registers as the XOR swap and is at least as fast, and often faster***. The XOR swap is also much less readable and completely opaque to anyone unfamiliar with the technique._ In short then, just use a native swap, i.e. rotate values using a temp variable. — ryyker, Jul 11 '17 at 14:59

cxw · Accepted Answer · 2017-07-11T14:46:10.343

Edit

The short answer: You cannot perform bitwise operations on pointers. Unfortunately, you cannot perform bitwise operations on floats, either! Don't use the XOR swap for float values.

Original

The commenters gave you the short answer. Now for my take on the long answer —

Bitwise operations such as ^ are defined for integers. However, a pointer is not necessarily an integer. On real-mode x86, a pointer includes, or is in some way related to, two integers: a segment and an offset (additional info). Worse, those two integers overlap, so changes to one also change the other. Therefore, there is no single, unambiguous way to define ^ or other bitwise operations for pointers.

Lots of code does assume that pointers can be treated as integers, since segmented addressing is less common than it used to be. However, the C standard still has to support less-common architectures, so does not define bitwise operations on pointers.

Rest of edit

I see that the example you linked uses pointers. That is because, in C, you have to use pointers to pass values back to the caller of a function through parameters. The code you linked is:

void xorSwap (int *x, int *y) {
     if (x != y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

(enwiki, CC-BY-SA 3.0). You could call that in your context as

if(x[i]!=x[j]) xorSwap(&x[i], &x[j]);

if x were an array of ints, and it would swap the contents of the array elements, as I think you expect. When you are using XOR swap directly, rather than via a function, you do not need to use pointers at all. For example:

if(x[i]!=x[j]) {
    x[i] ^= x[j];
    x[j] ^= x[i];
    x[i] ^= x[j];
}

should work, again, provided that x is int and not float.

@Olaf cxw is talking about pointers, not floats. The op is using BW operation on pointers. — Eugene Sh., Jul 11 '17 at 14:38
@EugeneSh. read my comment again. The code is not what the text states, The question is unclear missing a correct mcve. — too honest for this site, Jul 11 '17 at 14:38
1) There is no "_XOR trick". 2) Don't use that way at all. Leave optimizations to the compiler. 3) it is not guaranteed to be faster, could be slower as well. — too honest for this site, Jul 11 '17 at 14:45

izlin · Answer 2 · 2017-07-11T14:57:38.920

You want to swap the address and not the actual value if you do a ^= b with pointers. Instead you should use the values. The next problem is that you want to XOR floats and that is not possible. Instead you could take the single bytes of your float and XOR them:

void swap( float * one, float * two){
    unsigned char* a= (unsigned char *)one;
    unsigned char* b= (unsigned char *)two;

    for(int i = 0; i < sizeof(float); i++){
        *a ^= *b;
        *b ^= *a;
        *a ^= *b;
        a++;
        b++;
    }
}

int main(void) {
    float one = 1.0, two = 2.0;

    swap(&one, &two);
    printf("%f    %f", one, two); // prints 2.0000    1.0000
    return 0;
}

This is much additional work, not worth the effort and pretty sure slower. You can use XOR swapping for integer and regular swapping with a temp variable for floats.

Why do you recommend XOR swapping for ints? It is clearly an inferior solution. — geza, Jul 11 '17 at 14:56
@geza I don't wanted to recommend it, maybe I choose the words a bit misleading. I wanted to say that you can use it with integers if you want. — izlin, Jul 11 '17 at 14:59

zerek · Answer 3 · 2017-07-11T14:37:21.300

-1

It is normal.

  float* a= x[i];

is invalid. Your array of float is x. You are trying to get a value from the array. So it should be :

float a = x[i];
float b = x[j];

If you put an '*', you make a pointer. Anyway, as Wikipedia shows, it should not work. Only on integers.

edited Jul 11 '17 at 14:37

answered Jul 11 '17 at 14:33

zerek

253
1
12

Oh sorry, I add the rest of the answer – zerek Jul 11 '17 at 14:34
I've fixed it in my post please have a look again!! – A.nechi Jul 11 '17 at 14:34
1

Still, the proposed method of swapping is not going to work on floats – Eugene Sh. Jul 11 '17 at 14:36

Pointer issue when applying the XOR swap algorithm

3 Answers3

Edit

Original

Rest of edit