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

Question

Jon Bentley在他的书《编程珠玑》第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位
• test返回第i位的值

现在，我不理解这些函数是如何实现它们的。我无法弄清楚在这三个函数中发生的所有位操作。

- ardsrk

---

我将接受Laurence的答案，因为它帮助我在基本层面上理解了程序的机制。 - ardsrk

Answer 1

前三个常量是相互关联的。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] 的目的就是这个。您还可以将此写成 a[i/BITSPERWORD]（实际上，如果编译器具有合理的优化器，则可能会得到相同或非常相似的代码）。

现在我们知道了我们想要的 a 的哪个元素，我们需要找出哪个位。真正的情况是，我们想要余数。我们可以使用 i%BITSPERWORD 来实现这一点，但结果表明，i&MASK 是等效的。这是因为 BITSPERWORD 是2的幂（在本例中为2^5），而 MASK 是设置了底部5位的值。

- Laurence Gonsalves

---

这是我想表达的人类语言版本 :) 加1分可读性！ - xtofl

@Laurence Gonsalves 很好的分析，点赞 :) - Tracy

Answer 2

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

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

换句话说（对于N < 10且要排序3个数字4、6、2），从一个空的10位数组开始（通常是一个整数）。

0000000000

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

0000100000

读取6并在数组中设定该位

0000101000

读取2并在数组中设置该位

0010101000

遍历数组并打印每个二进制位为1的位置。

2、4、6

已排序。

- Mihai Toader

---

没关系。我感谢你的参与。 - ardsrk

恰巧，那就是我没有完全理解的部分。谢谢。 - xtofl

Answer 3

从set()开始：
将一个整数向右移5位相当于除以32。这样做是为了找出该比特位于哪个整数中。
MASK是0x1f或31。对地址进行AND运算可以得到该整数中的比特索引。这与将地址除以32后取余数相同。
将1左移比特索引（"1<<(i & MASK)"）会得到一个整数，该整数在给定位置上只有1个比特被设置。
OR运算可设置比特位。
行 "int sh = i>>SHIFT;" 是一行无用代码，因为它们在下面没有再次使用sh，而是重复使用了 "i>>SHIFT"。

clr()基本上与set相同，不同之处在于，它不是使用OR运算符和1<<(i & MASK)来设置比特位，而是使用反码进行AND运算来清除比特位。test()使用1<<(i & MASK)进行AND运算来测试比特位。

位排序还可以从列表中删除重复项，因为它只计算每个整数的1次。使用整数而不是比特来计数超过1个的排序称为基数排序。

- David

---

quinmars，您能否详细说明一下？ - ardsrk

他是对的。我想我描述的是计数排序，而不是基数排序。 - David

在基数排序中，您按位排序；从将第一个（或最后一个）数字放在一起开始，然后继续下一个数字，依此类推。请参见http://en.wikipedia.org/wiki/Radix_sort - quinmars

Answer 4

位运算技巧被用作一种特殊的寻址方案，适用于行大小为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。

当您在内存中使用每行1个32位的单词进行优化时，您会发现可以使用以下方法设置列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的幂次方，则模运算符可以被逻辑与运算符替代，而除法运算符也可以被移位运算符替代。

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

这最终归结为非常密集但对于不熟悉位操作的人来说难以理解的符号表示法。

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

但是我不认为该算法适用于每个单词40位的情况。

- xtofl

Answer 5

引用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

- Viren

Answer 6

一些疑问： 1. 为什么需要32位？ 2. 我们能否通过创建一个HashMap，将键从0000000到9999999，并且值为0或1，基于位的存在/不存在，在Java中实现此操作？这样的程序有什么影响？

- Ved Antani