c - 对于基数排序，我的常量掩码值应该是多少？

Question

我的一门计算机科学类(class)遇到了一个问题，我必须编写一个 LSD 基数排序来对无符号整数(+ 或 -)进行排序。假设要排序的值为32位整数值。

规定是我的掩码必须是一个常量值，这就是我的问题所在。如果我对一个 32 位整数进行 & 按位运算，其中每个数字由 4 位(十六进制表示)表示，我的掩码应该是 28 吗？ (因为我希望二进制中有 28 位 1)

此外，如果有人发现任何其他错误，请您注意这些错误吗？

#define BITS_PER_PASS 4
#define NUM_PASSES 8
#define NUM_BUCKETS 16
#define MASK 28

int *buckets[NUM_BUCKETS];
int bucket_sizes[NUM_BUCKETS];

void radix_sort( int *values, int n )
{
    int i, j;
    int bucket_index;
    int *p;

    for( i=0; i < NUM_PASSES; i++ )
    {
        for( j=0; j < NUM_BUCKETS; j++ )
        {
            bucket_sizes[j]=0;
        }

        for( j=0; j < n; j++ )
        {
            bucket_index = (values[j] & MASK) >> BITS_PER_PASS*i; //QUESTION
            buckets[j][ bucket_sizes[bucket_index]]=values[j];
            bucket_sizes[bucket_index]++;
        }

        p = values;

        for( j=0; j < NUM_BUCKETS; j++ )
        {
            memcpy((void *)p, (void *)buckets[j], sizeof(int)*bucket_sizes[j]);
            p+=bucket_sizes[j];
        }
    }
}

我还想补充一点，所有定义的常量和全局变量都是强制性的，因为我被告知在基数排序中使用它们。

Answer 1

而不是这个:

int *buckets[NUM_BUCKETS];
int bucket_sizes[NUM_BUCKETS];
...
buckets[j][ bucket_sizes[bucket_index]]=values[j];

建议:

int buckets[NUM_BUCKETS];
int bucket_size[NUM_BUCKETS];
...
buckets[bucket_size[bucket_index]]=values[j];

关于这些行:

bucket_index = (values[j] & MASK) >> BITS_PER_PASS*i;

我希望能提取 4 位，例如:

bucket_index = (values[j] >> BITS_PER_PASS*i) & MASK;

其中 MASK 将为 0x0F，因为尝试选择 16 个不同的“存储桶”之一(其中 &0x0F 将产生 0...15 范围内的值)