此位排序代码中的位操作如何工作？

Jon Bentley 在他的《Programming Pearls》一书的第一栏介绍了一种使用位向量对非零正整数序列进行排序的技术。

我已经从以下位置获取了程序 bitsort.chere https://web.archive.org/web/20080725054521/http://www.cs.bell-labs.com/cm/cs/pearls/code.html并将其粘贴在下面：

/* 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 位的值

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

前 3 个常数是相互关联的。 BITSPERWORD 是 32。您需要根据您的编译器+体系结构进行设置。 SHIFT 为 5，因为 2^5 = 32。最后，MASK 为 0x1F，即二进制的 11111（即：底部 5 位已全部设置）。等效地，MASK = BITSPERWORD - 1。

位集在概念上只是一个位数组。该实现实际上使用了一个 int 数组，并假设每个 int 有 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 位。