question about bitonic sort algorithms

[luohj29]

hey! I have learned a lot from your code. About the Bitonic sort algorithm, I don'k know how to understand about :

1. "ij = i ^ j" , why ^ is needed?
2. "i & k", why & is needed?
   those are sentences in the Bitonic sort kernel. I am learning the Bitonic sort Algorithm, but cannot relate to this part in your code. I would be grateful if you could answer my question! @rbga

[rbga]

ij = i ^ j,

where ij is basically j bits away from i in binary terms. This is to ensure proper pairing for sorting as this avoids duplicate pairs and such.
Each element gets exactly one partner at the correct distance
No duplicates
No self-pairing

This is basically log(total elements size) if you think about it. If total elements is 8, it gives you 4, 2, 1 where you sort the pairs that are 4 apart, then 2 apart, then 1 apart. THIS you do over and over in a loop until entire elements are sorted.

i & k determines whether the current element is in a bitonic sequence that should be sorted ascending or descending. If i & k == 0, sort ascending. If i & k != 0, sort descending.

[luohj29]

thanks for reply. You helped me a lot : )