기수 정렬. 왜 Xor인가?

Question

기수 정렬 알고리즘을 연구했지만 원본 소스 코드 중 일부를 이해할 수 없었습니다. 그것의 for (i = 0; i < len; i++) x[i] ^= INT_MIN;

내가 그 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; 
} 

는 모르겠지만 나는이 상황에서이 연산자의 사용을 이해하지 않습니다.

Answer 1

MSB (최상위 비트)를 토글합니다.

INT_MIN은 사용하는 컴파일러와 시스템에 따라 다르지만 일반적으로 16 진수의 0x80000000과 비슷할 것이며 이진수는 10000 ... 0과 같습니다. 당신이 그것을 토글 한 당신을 어떤 비트를 XOR 경우

:

그 라인이 실행될 때,, x의 가장 높은 비트 [i]는 전환되고

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 

. 그것이 0이면 지금은 1입니다. 그것이 하나라면, 이제는 0입니다.

간단히 말해 : XOR 임의 값 X는 0이고, 원래 값은 X, X 값은 X, X는 1, X의 보수는 X입니다.

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