Radix Sort. Почему Xor?

Question

Я изучал алгоритм сортировки radix, но я не мог понять некоторые из исходного исходного кода.

static void rad_sort_u(unsigned *from, unsigned *to, unsigned bit) 
{ 
    if (!bit || to < from + 1) return; 

    unsigned *ll = from, *rr = to - 1,tmp; 
    while (1) { 
     /* find left most with bit, and right most without bit, swap */ 
     while (ll < rr && !(*ll & bit)) ll++; 
     while (ll < rr && (*rr & bit)) rr--; 
     if (ll >= rr) break; 
     swap(*ll, *rr); 
    } 

    if (!(bit & *ll) && ll < to) ll++; 
    bit >>= 1; 

    rad_sort_u(from, ll, bit); 
    rad_sort_u(ll, to, bit); 
} 

/* sort signed ints: flip highest bit, sort as unsigned, flip back */ 
static void radix_sort(int *a, const size_t len) 
{ 
    size_t i; 
    unsigned *x = (unsigned*) a; 

    for (i = 0; i < len; i++) 
      x[i] ^= INT_MIN; 

    rad_sort_u(x, x + len, INT_MIN); 

    for (i = 0; i < len; i++) 
      x[i] ^= INT_MIN; 
} 

Я не знаю, почему его использование этой линии for (i = 0; i < len; i++) x[i] ^= INT_MIN;

Я знаю его XOR, но я не понимаю, использование этого оператора в этом контексте.

Answer 1

Он переключает MSB (самый старший бит).

INT_MIN различается в зависимости от используемого компилятора и системы, но, как правило, это будет что-то вроде 0x80000000 в шестнадцатеричном виде, которое будет оцениваться примерно в 10000 ... 0 в двоичном формате.

Если вы XOR любой бит с одним, вы переключаетесь ему:

eg: if y = A xor B 

y | A B 
==+==== 
0 0 0 
1 0 1 
1 1 0 
0 1 1 

y | A 1 
==+==== 
1 0 1 
0 1 1 

Therefore 
A xor 1 = !A 

Таким образом, когда эта линия выполнена, старший бит х [я] в настоящее время переключается. Если он был равен нулю, теперь он один. Если бы он был одним, то теперь он равен нулю.

Вкратце: XOR любое значение, X, с 0, вы получаете исходное значение, X. XOR любое значение X, с 1, вы получаете дополнение X,! X.

Y | X A 
===+==== 
X X 0 
!X X 1