Strange bitwise XOR behavior

Question

Why would the following "swap" action fail at random times?

int i,p,a[11] = {0,1,2,3,4,5,6,7,8,9,10 };

srand(time(0));

for (i=0;i<11;i++)
{
    p = rand() % 11;
    a[i] = a[i] ^ a[p];
    a[p] = a[i] ^ a[p];
    a[i] = a[i] ^ a[p];
}

It is not so different from the the logic in this answer
It will work for a 3/4 runs and then start to duplicate 0

Tried it in C and C++, same results

[edit]
Solved by initializing p=0 and replacing the relevant line with while (p==i) p = rand() % 11;

Update: The reason NOT to use xor (see Mark Byers' answer and comment)

See e.g. http://stackoverflow.com/questions/375351/most-efficient-way-to-randomly-sort-shuffle-a-list-of-integers-in-c-sharp — usr, Jul 03 '12 at 20:26

score 6 · Accepted Answer · answered Jul 03 '12 at 19:26

6

If p happens to be the same as i, then a[i] ^ a[p] will be zero, and the rest of the function fails.

Statistically, your code actually has a 65% chance of failing in this way.

Make sure that, when generating p, it is not the same number as i. For instance:

p = rand() % 10;
if( p >= i) p++;

answered Jul 03 '12 at 19:26

Niet the Dark Absol

320,036
81
464
592

or check `i == p` before swapping. – kennytm Jul 03 '12 at 19:31
@KennyTM: done that, thanks. Even stranger is that I debugged and watched the values but it didn't register :( - break-time and stop coding till tomorrow for me now. – slashmais Jul 03 '12 at 19:40

score 5 · Answer 2 · answered Jul 03 '12 at 19:26

5

When i equals p then a[i] ^ a[p] becomes zero. Your "swap" operation is broken.

To swap you should use a temporary variable:

int temp = a[i];
a[i] = a[p];
a[p] = temp;

Don't use the XOR hack.

answered Jul 03 '12 at 19:26

Mark Byers

811,555
193
1,581
1,452

Just read that div-by-2 question, so I won't take your statement (/command ;) lightly: why should I avoid using this "hack"? – slashmais Jul 03 '12 at 20:00
1

@slashmais: Because it can break for exactly the reason you demonstrated. Yes you can fix it, but if you had swapped the variables the normal way, you wouldn't have needed to fix it in the first place. Also see Wikipedia: [Reasons for avoidance in practice](http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice). One of the reasons stated there is that the normal swap is faster. – Mark Byers Jul 03 '12 at 20:52

score 1 · Answer 3 · answered Jul 03 '12 at 19:27

1

Because p is randomly equal to i. In this case, a[i] instantly becomes 0.

answered Jul 03 '12 at 19:27

Puppy

144,682
38
256
465

score 1 · Answer 4 · answered Jul 03 '12 at 19:27

1

If i == p then a[i] will store 0.

answered Jul 03 '12 at 19:27

UmNyobe

22,539
9
61
90

score 1 · Answer 5 · answered Jul 03 '12 at 20:43

As an development practice, XOR swaping is not recommended. But if you are using logic for fun then use this line which will ensure that p will not same as i.

p = ((rand()%10)+(i+1))%11;

or

p = ((rand()%(count-1))+(i+1))%count;

But notice this trick is not good for performance perspective because it requires two modules operator and one addition (or subtraction). Use the exact comparison (which is the fastest comparison operator) and add 1 if they same.

p = rand()%10;
if (p == i) p++;

Strange bitwise XOR behavior

5 Answers5