帮助我了解这个"编程珍珠"bitsort程序

StackOverflow https://stackoverflow.com/questions/1050253

  •  20-08-2019
  •  | 
  •  

题

乔恩*宾利在第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，设置和测试正在进行的工作和他们解释如下：(请纠正我，如果我错了这里)。

  • clr清除ith位
  • 设置ith位
  • 测试回报的价值在ith位

现在，我不明白怎么能做什么他们这样做。我无法弄清楚所有的位操作发生在这三个职能。

请帮助。

有帮助吗？

解决方案

第3常量是互相关。BITSPERWORD为32。这你想要的设定基础上编译器+架构。移5，因为2^5=32.最后，掩0x1F其是11111在二元(即：底部的5位全都设置)。等效地、掩模=BITSPERWORD-1.

特集在概念上只是一系列的位。这个执行实际上使用的一系列整数，并假定的32位每int。所以每当我们想到设置，清除或测试(阅读)的一位我们需要弄清两件事情：

  • 这int(阵列)是它在
  • 它的int的位是我们在谈论

因为我们假设32位/int，我们就可以分由32(和截断)，获得列指数，我们想要的。除32(BITSPERWORD)是相同的转换到右边的5(移)。所以这是什么样的一个[i>>移]位。你也可以写这作为[i/BITSPERWORD](事实上，你可能会得到相同或非常相似码的假设编译器具有的合理优化器).

现在我们知道这一元素，我们希望，我们需要找出它的位。真的，我们希望剩余部分。我们可以这样做与我%BITSPERWORD，但事实证明，我&面具是等同的。这是因为BITSPERWORD是2(2^5在这种情况下)和掩底5位的所有设置。

其他提示

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

  • 保留一个位阵列的长n 位。
  • 清楚的位阵列(第一，在主要的).
  • 阅读的项目之一的人(他们所有人都必须是不同的).
    • 设置我个位在位阵列，如果读数是我.
  • 迭代位阵列。
    • 如果位置然后打印的位置。

或者换句话说(N < 10排序的3个数字的4,6,2)0

开始有一个空的10位阵列(aka一个整数通常)

0000000000

读4和定位阵列中的..

0000100000

读6和定位阵列

0000101000

读2和定位阵列

0010101000

迭代的阵和打印的每个位置在哪位被设置为一个。

2, 4, 6

排序。

开始设置():
右转移的5是一样分割的32个。它不，要找到其int位。
掩0x1f或31。安定的地址给这位索引内int。它是相同的其余部分分割地址通过32个。
移1留下点指数("1<<(i&掩)")的结果在整数，其中只有1位在指定位置。
"或"定点。
线"int sh=i>>移；"是一种浪费，因为他们没有使用sh再次下它，而不是仅仅重复"i>>移"

clr()基本上是相同的设置除外，而不是"或"1<<(i&掩)设置位，阿富汗国家发展战略与反清点。test()阿富汗国家发展战略1<<(i&掩)测试位。

该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.

当你优化这种存在使用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;

因此，要设置我个点,你可以这样做：

bits[ i%BITSPERROW ] |= 1 << (linear_address / BITSPERROW );

一个额外问题是，该模的操作者可以替换为一个合乎逻辑的，和/经营者可以替换为一个转变，过，如果第二个操作数是力量的两个。

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到9999999 和价值0或1根据存在/缺点？有什么影响 对于这样一个程序？

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top