帮我理解这个"编程珍珠"bitort程序

Question

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

我从这里获取了programort.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位
• test返回第i位的值

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

请帮忙.

Answer 1

前3个常数是相互关联的.BITSPERWORD是32.您要根据编译器+体系结构进行设置.SHIFT为5,因为2 ^ 5 = 32.最后,MASK为0x1F,二进制为11111(即:底部5位全部置位).等价地,MASK = BITSPERWORD - 1.

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

• 哪个int(数组)是在
• 我们在谈论哪个int的位

因为我们假设每个int有32位,我们可以除以32(和truncate)来获得我们想要的数组索引.除以32(BITSPERWORD)与向右移动5(SHIFT)相同.这就是a [i >> SHIFT]位的内容.您也可以将其写为[i/BITSPERWORD](实际上,假设您的编译器具有合理的优化器,您可能会得到相同或非常相似的代码).

现在我们知道了我们想要的哪个元素,我们需要找出哪个位.真的,我们想要剩下的.我们可以用i%BITSPERWORD做到这一点,但事实证明i&MASK是等价的.这是因为BITSPERWORD是2的幂(在这种情况下为2 ^ 5),MASK是所有设置的底部5位.