11

Jon Bentley 在他的书 Programming Pearls 的第 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 和 test 的功能并在下面解释它们：（如果我在这里错了，请纠正我）。

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

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

4

6 回答 6

23

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

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

  • 它在（数组的）哪个 int 中
  • 我们在谈论哪个 int 位

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

现在我们知道了我们想要 a 的哪个元素，我们需要弄清楚是哪一个位。真的，我们想要剩下的。我们可以用 i%BITSPERWORD 做到这一点，但事实证明 i&MASK 是等价的。这是因为 BITSPERWORD 是 2 的幂（在这种情况下为 2^5），而 MASK 是所有设置的低 5 位。

于 2009-06-26T17:56:03.817 回答
4

基本上是一个桶排序优化：

  • 保留一个长度为 n 位的位数组。
  • 清除位数组（首先在 main 中）。
  • 逐一阅读项目（它们必须都是不同的）。
    • 如果读取数为 i，则设置位数组中的第 i 个位。
  • 迭代位数组。
    • 如果该位已设置，则打印该位置。

或者换句话说（对于 N < 10 并排序 3 个数字 4、6、2）0

从一个空的 10 位数组开始（通常是一个整数）

0000000000

读取 4 并设置数组中的位..

0000100000

读取 6 并设置数组中的位

0000101000

读取 2 并设置数组中的位

0010101000

迭代数组并打印位设置为 1 的每个位置。

2、4、6

排序。

于 2009-06-26T17:34:44.343 回答
3

从 set() 开始：
5 的右移与除以 32 相同。它这样做是为了找到该位在哪个 int 中
。MASK 是 0x1f 或 31。与地址进行与运算给出了 int 内的位索引。它与将地址除以 32 的余数相同。
将 1 左移位索引 ("1<<(i & MASK)") 会导致在给定位置集中只有 1 位的整数。
ORing 设置位。
行“int sh = i>>SHIFT;” 是一个浪费的行，因为他们没有在它下面再次使用 sh ，而是只是重复了“i>>SHIFT”

clr() 与 set 基本相同，除了不是与 1<<(i & MASK) 进行 ORing 来设置位，而是与逆运算以清除位。test() AND 与 1<<(i & MASK) 来测试位。

位排序还会从列表中删除重复项，因为每个整数最多只能计数 1 个。使用整数而不是位来计数超过 1 的排序称为基数排序。

于 2009-06-26T17:41:01.933 回答
2

位魔法用作一种特殊的寻址方案，适用于为 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 );

一个额外的问题是，如果第二个操作数是 2 的幂，模运算符可以用逻辑 AND 代替，/ 运算符也可以用移位代替。

a % BITSPERROW == a & ( BITSPERROW - 1 ) == a & MASK
a / BITSPERROW == a >> ( log2(BITSPERROW) ) == a & SHIFT

这最终归结为非常密集但难以理解的比特混蛋不可知符号

a[ i >> SHIFT ] |= ( 1 << (i&MASK) );

但我没有看到算法适用于例如每字 40 位。

于 2009-06-26T18:35:46.700 回答
0

引用 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
于 2014-07-08T19:37:15.627 回答
-3

几个疑惑： 1. 为什么需要32位？2. 我们可以在 Java 中通过创建一个 HashMap 来做到这一点吗？键从 0000000 到 9999999 并且值 0 或 1 基于位的存在/不存在？对这样的计划有何影响？

于 2009-09-14T12:01:20.683 回答