오른쪽 (LSB) 기수 - 2의 보수를 처리하는 방법?

Question

정수에 대해 오른쪽/LSB 기수 정렬을 구현하려고 시도 중이고 일단 작동하면 병렬 처리하려고 시도합니다. 내 순차 코드는 부호없는 숫자에 대해서는 잘 작동하지만 일단 음의 정수를 던지면 부호있는 비트를 보지 않고 0부터 까지 양수 (소트 된 정수)로 끝납니다. n은 음수와 섞인입니다.) 정수는 -n부터 -1까지입니다.

public class SeqRadix { 
    static void radix2(int[] a) { 

     // 2 digit radixSort: a[] 
     int max = a[0]; 
     int numBit = 2; 
     int n = a.length; 

     // a) find max value in a[] 
     for (int i = 1; i < n; i++){ 
      if (a[i] > max) { 
       max = a[i]; 
      } 
     } 
     while (max >= (1 << numBit)){ 
      numBit++; // digits in max 
     } 
     // decide num of bits in bit1 and bit2 
     int bit1 = numBit/2, bit2 = numBit - bit1; 
     int[] b = new int[n]; 
     radixSort(a, b, bit1, 0); // first digit from a[] to b[] 
     radixSort(b, a, bit2, bit1);// second digit, back from b[] to a[] 
    } // end 

    /** 
    * Sort a[] on one digit ; number of bits = maskLen, shiftet up �shift� 
    * bits 
    */ 
    static void radixSort(int[] a, int[] b, int maskLen, int shift) { 
     int acumVal = 0, j, n = a.length; 
     int mask = (1 << maskLen) - 1; 
     int[] count = new int[mask + 1]; 

     // b) count=the frequency of each radix value in a 
     for (int i = 0; i < n; i++) { 
      count[(a[i] >> shift) & mask]++; 
     } 

     // c) Add up in 'count' - accumulated values 
     for (int i = 0; i <= mask; i++) { 
      j = count[i]; 
      count[i] = acumVal; 
      acumVal += j; 
     } 
     // c) move numbers in sorted order a to b 
     for (int i = 0; i < n; i++) { 
      b[count[(a[i] >> shift) & mask]++] = a[i]; 
     } 
    }// end radixSort 
}// end SekvensiellRadix 

LSB들에 첫번째 종류 시작하고 점점 더 중요한 비트, 마지막 2의 보수로/부호 비트가 잡히지 않습니다 보인다 :

여기 내 코드입니다. 미리 감사드립니다!

Answer 1

당신이해야 할 기호에 비교 작업을 반전됩니다 : 당신은 거기뿐만 아니라 (언어에서 지원하지 않는 자바 수단) 부호없는 비교를 사용하기 때문에 비교하기 전에 비트 (31)를 뒤집어 야 비트. 다른 모든 비트의 경우 0 < 1이지만 부호 비트의 경우 1 < 0을 사용합니다. 0에서 30까지의 비트를 정렬 할 때 (분명히 32 비트 정수의 경우) 크기의 정수을 정렬합니다. 절대적으로 아닙니다. 한 자리 이동이기 때문에, 같은 부호의 다른 모든 정수에 상대적입니다. 우리 모두가 필요합니다. 우리는 숫자가있는 경우

그래서, {5, -1, 3, 2, -3은 -8} (단순 서명 된 4 비트) :

0101 = 5 
1111 = -1 
0011 = 3 
0010 = 2 
1101 = -3 
1000 = -8 

비트 2 우리까지 정렬 한 후 have :

1 000 = -8 
0 010 = 2 
0 011 = 3 
0 101 = 5 
1 101 = -3 
1 111 = -1 

음수의 각각은 다른 음수에 비례하여 증가하는 순서로 정렬됩니다. (마찬가지로 긍정적 인 점이 있습니다.) 자, 부호 비트의 비교를 위해 우리는 1 < 0라고 말합니다. 그것은 모든 음수를리스트의 맨 앞으로 옮기고 안정된 정렬 메커니즘을 사용하기 때문에 모든 음수는 서로 상대적으로 같은 위치에 있습니다. (. 또, 마찬가지로 긍정적 인 경우) 결국

우리는 우리의 목록을 오름차순으로 정렬 한 :

1000 = -8 
1101 = -3 
1111 = -1 
0010 = 2 
0011 = 3 
0101 = 5 

Answer 2

그들에 결정을 내릴 때 당신은 단순히 31 비트를 반전시켜 모두가 서명되지 않은 값을 int로 변환 할 필요가

:

unsigned = signed^0x80000000; 

다른 방법을 좀 더 편리하게는, 구현을 기반으로 한 모든 의사 결정의 결과를 반전하는 것을 발견하면,

편집 : 최대 값을 찾으려고하면 이미 시작됩니다. 최대 값을 찾는 방법은 최대 31 비트로 값을 찾지 못할 것입니다.

// a) find max value in a[] 
    for (int i = 1; i < n; i++){ 
     if ((a[i]^0x80000000) > (max^0x80000000)) { 
      max = a[i]; 
     } 
    }