java - Right (LSB) radix -- 如何处理 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

您需要做的是反转符号位上的比较操作。对于每隔一位，0 < 1 , 但对于符号位，我们使用 1 < 0 .当您对位 0 到 30 进行排序时(对于 32 位整数，显然)，您对该整数的ma​​gnitude 进行了排序。不是绝对的，因为有一个移位，但相对于所有其他具有相同符号的整数，这就是我们所需要的。

因此，如果我们有数字 {5, -1, 3, 2, -3, -8}(为简单起见，有符号 4 位):

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

排序到第 2 位后，我们有:

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