c - 这个位排序代码中的位操作是如何工作的？

Question

Jon Bentley 在他的编程珍珠一书的第 1 栏中介绍了一种使用位 vector 对非零正整数序列进行排序的技术。

我从 here 中获取了程序 bitsort.c并将其粘贴在下面:

/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

/* bitsort.c -- bitmap sort from Column 1
 *   Sort distinct integers in the range [0..N-1]
 */

#include <stdio.h>

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000

int a[1 + N/BITSPERWORD];

void set(int i) 
{
    int sh = i>>SHIFT;
    a[i>>SHIFT] |=  (1<<(i & MASK)); 
}
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

int main()
{   int i;
for (i = 0; i < N; i++)
    clr(i);

    /*Replace above 2 lines with below 3 for word-parallel init
    int top = 1 + N/BITSPERWORD;
    for (i = 0; i < top; i++)
    a[i] = 0;
    */

while (scanf("%d", &i) != EOF)
    set(i);
for (i = 0; i < N; i++)
        if (test(i))
    printf("%d\n", i);
return 0;
}

我理解 clr、set 和 test 函数在做什么，并在下面解释它们:(如果我在这里错了，请纠正我)。

• clr 清除第 i 位
• set 设置第 i 个位
• 测试返回第i位的值

现在，我不明白这些函数是如何做的。我无法弄清楚这三个函数中发生的所有位操作。

Answer 1

前 3 个常量是相互关联的。 BITSPERWORD 是 32。您需要根据您的编译器+架构来设置它。 SHIFT 为 5，因为 2^5 = 32。最后，MASK 为 0x1F，二进制为 11111(即:低 5 位全部设置)。等价地，MASK = BITSPERWORD - 1。

bitset 在概念上只是一个位数组。这个实现实际上使用了一个整数数组，并假设每个整数有 32 位。因此，每当我们想要设置、清除或测试(读取)位时，我们需要弄清楚两件事:

• 它在(数组的)哪个int中
• 我们在谈论 int 的哪些位

因为我们假设每个 int 有 32 位，所以我们可以除以 32(并截断)以获得我们想要的数组索引。除以 32 (BITSPERWORD) 与右移 5 (SHIFT) 相同。这就是 a[i>>SHIFT] 位的意义所在。您也可以将其写为 [i/BITSPERWORD](事实上，假设您的编译器具有合理的优化器，您可能会得到相同或非常相似的代码)。

现在我们知道我们想要 a 的哪个元素，我们需要弄清楚是哪一位。真的，我们想要剩下的。我们可以用 i%BITSPERWORD 做到这一点，但事实证明 i&MASK 是等价的。这是因为 BITSPERWORD 是 2 的幂(在本例中为 2^5)，而 MASK 是全部设置的底部 5 位。