2

基数ソートアルゴリズムを勉強していましたが、元のソースコードの一部を理解できませんでした。

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 は知っていますが、このコンテキストでのこの演算子の使用法がわかりません。

4

1 に答える 1

2

MSB（最上位ビット）を切り替えています。

INT_MIN は、使用しているコンパイラとシステムによって異なりますが、一般的には 16 進数で 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

したがって、その行が実行されると、x[i] の最上位ビットがトグルされます。ゼロだった場合、現在は 1 です。1 だった場合、現在は 0 です。

つまり、0任意の値 X を で XOR すると、元の値 X が得られます。任意の値 X を 1 で XOR すると、X の補数である !X が得られます。

 Y | X A
===+====
 X   X 0
!X   X 1
于 2012-05-08T16:47:56.307 に答える