帮我理解这个“编程珍珠”bitort程序
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 #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<>SHIFT] &= ~(1<>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的function正在做什么，并在下面解释:(如果我错了，请纠正我）。
- clr清除了第i位
- set设置第i位
- test返回第i位的值
现在，我不明白这些function是如何做的。 我无法弄清楚这三个函数中发生的所有位操作。
请帮忙。
前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做到这一点，但事实certificatei＆MASK是等价的。 这是因为BITSPERWORD是2的幂（在这种情况下为2 ^ 5），MASK是所有设置的底部5位。
基本上是优化的桶排序：
- 保留长度为n位的位数组。
- 清除位数组（首先是在main中）。
- 逐个阅读这些项目（它们必须完全不同）。
- 如果读取的数字是i，则在位数组中设置第i位。
- 迭代位数组。
- 如果设置了该位，则打印该位置。
或者换句话说（对于N <10和对3号，4号，6号，2号）0
从空的10位数组开始（通常也称为一个整数）
0000000000
读取4并设置数组中的位..
0000100000
读取6并设置数组中的位
0000101000
读取2并设置数组中的位
0010101000
迭代数组并打印位设置为1的每个位置。
2,4,6
排序。
从set（）开始：
右移5与除以32相同。这样可以找到该位所在的int。
MASK为0x1f或31.与地址进行AND运算会得到int内的位索引。 它与将地址除以32的其余部分相同。
通过位索引向左移位1（“1 <<（i＆MASK）”）导致在给定位置集中仅具有1位的整数。
ORing设置了一下。
行“int sh = i >> SHIFT;” 是一条浪费的线，因为他们没有在它下面再次使用sh，而只是重复“i >> SHIFT”
clr（）基本上与set相同，除了使用1 <<（i＆MASK）进行OR运算来设置该位，它使用反向AND来清除该位。 test（）AND与1 <<（i＆MASK）来测试该位。
bitsort还将从列表中删除重复项，因为它每个整数最多只能计数1个。 使用整数而不是位来计算多于1的排序称为基数排序。
位魔术用作特殊寻址方案，适用于2的幂的行大小。
如果您尝试理解这一点（注意：我更倾向于使用每行位数而不是每字位数，因为我们在这里讨论的是一个位矩阵）：
// supposing an int of 1 bit would exist... int1 bits[BITSPERROW * N]; // an array of N x BITSPERROW elements // set bit at x,y: int linear_address = y*BITSPERWORD + x; bits + linear_address = 1; // or 0 // 0 1 2 3 4 5 6 7 8 9 10 11 ... 31 // . . . . . . . . . . . . . // . . . . X . . . . . . . . -> x = 4, y = 1 => i = (1*32 + 4)
语句linear_address = y*BITSPERWORD + x也表示x = linear_address % BITSPERWORD和y = linear_address / BITSPERWORD 。
当你通过使用每行32位的1个字在内存中优化它时，你会得到一个事实，即x列的一个位可以使用
int bitrow = 0; bitrow |= 1 << (x);
现在，当我们迭代这些位时，我们有线性地址，但需要找到相应的字。
int column = linear_address % BITSPERROW; int bit_mask = 1 << column; // meaning for the xth column, // you take 1 and shift that bit x times int row = linear_address / BITSPERROW;
所以要设置第i位，你可以这样做：
bits[ i%BITSPERROW ] |= 1 << (linear_address / BITSPERROW );
额外的问题是，模运算符可以用逻辑AND代替，如果第二个操作数是2的幂，则/运算符也可以由移位替换。
a % BITSPERROW == a & ( BITSPERROW - 1 ) == a & MASK a / BITSPERROW == a >> ( log2(BITSPERROW) ) == a & SHIFT
这最终归结为非常密集但难以理解的与bitfucker无关的表示法
a[ i >> SHIFT ] |= ( 1 << (i&MASK) );
但我没有看到算法适用于例如每字40位。
引用Bentleys在DDJ中的原始文章的摘录，这是代码在高级别上的作用：
/* phase 1: initialize set to empty */ for (i = 0; i < n; i++) bit[i] = 0 /* phase 2: insert present elements */ for each i in the input file bit[i] = 1 /* phase 3: write sorted output */ for (i = 0; i < n; i++) if bit[i] == 1 write i on the output file
一些疑问：1。为什么需要32位？ 2.我们可以通过创建一个包含0000000到9999999的密钥的HashMap，并根据该位的存在/不存在值0或1来在Java中执行此操作吗？ 对这样的计划有什么影响？