基数分类。为什么选择Xor？

我正在研究的基数排序算法，但我不明白一些原始源代码的。基数分类。为什么选择Xor？

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它，但我不明白，在这种情况下使用该运营商。

来源

2012-05-08 dreamcrash

提示：'INT_MIN'可能是'0x80000000'。 – Mysticial

阅读源代码中的评论，解释它。或者，可以在排序前将'2 ^（width-1）'添加到数字中作为'unsigned'，然后再排序。 –

这个代码在其递归中有一个*堆栈溢出*，这是不值得的。为了正确实现这个算法，你必须先递归到较小的一半，然后对较大的一半进行尾部递归（或者只是'goto top;'）。 –

它拨动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

所以，这一行被执行时，x的最高位[i]是被切换。如果它是零，现在是一个。如果它是一个，现在是零。总之：将任何值X与0异或，得到原始值X.XOR任意值X，用1得到X，！X的补数。

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

来源

2012-05-08 16:47:56 DevNull

'INT_MIX'？听起来像是一个很好的“最小”和“最大”混合。 :-) –

我刚刚在你的评论之前发现了这个错字。虽然不够快。我喜欢confuddle而不是帮助;） – DevNull

@Dogbert：我认为你只是停留在字符。 ; v） –

基数分类。为什么选择Xor？

回答

相关问题