乔恩·本特利在他的著作编程珍珠1栏目介绍了使用排序位向量的非零正整数序列的技术。
我已经拍摄节目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和测试正在做以下解释是：（请纠正我，如果我错了这里）。
- CLR清除第i位
- 集设置第i位
- 试验在第i位将返回值
现在，我不明白的功能怎么做他们做什么。 我无法弄清楚所有的位操作中，这三项功能发生。
请帮忙。
第3个常数是相互关联的。 BITSPERWORD是32.这你要根据你的编译器+架构设置。 SHIFT为5，因为2 ^ 5 = 32。最后，MASK是0x1F的是在11111的二进制（即：底部5位都被设置）。 等同地，MASK = BITSPERWORD - 1。
位集是概念性只是比特的阵列。 此实现实际上使用整数的数组，并假定每INT 32位。 所以每当我们要设置，清除或测试（读取）一点，我们需要弄清楚两件事情：
- 其中INT（所述阵列的）是它在
- 这是廉政局位，我们谈论的
因为我们假设每INT 32位，我们就可以通过32分（并截断）来得到我们想要的数组索引。 由32（BITSPERWORD）将是相同的由5（SHIFT）向右移动。 所以这是一个[我>> SHIFT]位是什么。 你也可以这样写一个[I / BITSPERWORD]（事实上，你可能会得到相同或非常相似的代码假设你的编译器有一个合理的优化器）。
现在，我们知道我们需要哪个的元素，我们需要弄清楚这一点。 真的，我们希望剩余部分。 我们可以用I％BITSPERWORD做到这一点，但事实证明，我和MASK等同。 这是因为BITSPERWORD是2的幂（2 ^ 5在这种情况下）和MASK是底部5位全部设置。
基本上是排序优化的桶：
- 预留长度为n位的位阵列。
- 清除该位阵列（第一对主）。
- 阅读项目一个一个地（它们都必须是不同的）。
- 迭代的比特阵列。
或者换句话说0（对于N <10和3个数字4，6,2排序）
先建立一个空的10比特阵列（也叫做一个通常整数）
0000000000
读4并设置位阵列中..
0000100000
读6并设置位阵列中的
0000101000
读2和设置该位阵列中的
0010101000
迭代阵列和打印每其中比特被设置为一个位置。
2，4，6
排序。
与集开始（）：
将5右移相同除以32它的是寻找一种诠释该位为英寸
MASK是为0x1F或31取与与地址给int中位索引。 这是同为除以32的地址的剩余部分。
在具有在给定的位置集只是1比特的整数移位1由位索引（“1 <<（I＆MASK）”）左边的结果。
或门设置位。
行 “INT SH = I >> SHIFT;” 是浪费线，因为他们没有在其下方再次使用sh和而不只是重复“I >> SHIFT”
CLR（）是基本相同组，除了代替与1 <<（I＆MASK）或运算来设定该位，它与运算与逆来清除该位。 用1 <<（I＆MASK）试验（+）与运算，以测试该位。
该bitsort也将从列表中删除重复的，因为它只能数到1元整数。 使用整数，而不是位的排序来算每超过1被称为基数排序。
该位魔术被用作与行大小为二的权力运作良好一种特殊的寻址方案。
如果你尝试理解这个（注：我宁愿使用位每行比位每一句话，因为我们在这里谈论的是位矩阵）：
// 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，并且/操作者可更换更换由移位也一样，如果第二操作数是二的幂。
a % BITSPERROW == a & ( BITSPERROW - 1 ) == a & MASK
a / BITSPERROW == a >> ( log2(BITSPERROW) ) == a & SHIFT
这最终归结到一个非常密集，但很难理解的，换了，bitfucker无关的符号
a[ i >> SHIFT ] |= ( 1 << (i&MASK) );
但我没有看到算法的工作，每字如40位。
引用来自宾利在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.我们能做到这一点在Java中通过创建从0000000的钥匙一个HashMap至9999999和价值观基础上的存在/不存在该位的0或1？ 什么是这样一个程序的影响？
