c - 基数排序。为什么异或？

Question

我正在研究基数排序算法，但我无法理解某些原始源代码。

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;

我知道它的异或，但我不明白这个运算符在这种情况下的用法。

Answer 1

它正在切换 MSB(最高有效位)。

根据我的理解，INT_MIN 因使用的编译器和系统而异，但它通常类似于十六进制的 0x80000000，其计算结果类似于二进制的 10000...0。

如果你用一个异或任何位，你切换它:

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

因此，当该行被执行时，x[i] 的最高位被切换。如果它是零，现在是一。如果它是一，现在为零。

简而言之:XOR 任何值 X，与 0，你得到原始值 X。XOR 任何值 X，与 1，你得到 X 的补码，!X。

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