I emailed the author to correct the section on XOR swap:
Once upon a time, when I was an aggressive young programmer, I tried to show off by replacing this swap:
void swap(int a, int b) {
int c = a;
a = b;
b = c;
}
with xor swap:
void swap(int a, int b) {
a ^= b;
b ^= a;
a ^= b;
}
and the program broke!
They’re not identical. The program was calling swap on array elements:
swap(&(array[i]), &(array[j]))
and occasionally i=j. That is, swap was being called with a==b. And that’s the difference: when you try to swap a ___location with itself. In that case, XOR as you know zeroed out the value in a. But that was also b. The other xors left the zero there. So, the array element was set to zero.
The original swap called on a single ___location did not modify the value. So, my XOR-swap show off introduced a huge bug!
Once upon a time, when I was an aggressive young programmer, I tried to show off by replacing this swap:
void swap(int a, int b) { int c = a; a = b; b = c; }
with xor swap:
void swap(int a, int b) { a ^= b; b ^= a; a ^= b; }
and the program broke!
They’re not identical. The program was calling swap on array elements:
and occasionally i=j. That is, swap was being called with a==b. And that’s the difference: when you try to swap a ___location with itself. In that case, XOR as you know zeroed out the value in a. But that was also b. The other xors left the zero there. So, the array element was set to zero.The original swap called on a single ___location did not modify the value. So, my XOR-swap show off introduced a huge bug!