如何在Java中编写比特排序程序？

大家好，我在理解Bentley经典编程珍珠中的bitsort程序时遇到了问题。我是Bitmask和Bitset的新手，所以我无法理解这些概念。其实计划是“如何整理磁盘文件？”，所以下面的代码是如何在Java中编写比特排序程序？

#include <stdio.h> 
#define BITSPERWORD 32 
#define SHIFT 5 
#define MASK 0x1F 
#define N 10000000 
int a[1 + N/BITSPERWORD]; 

void set(int i) { 
    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; 
}

可能有人请解释这段代码给我？如果可能的话，请提供Java版本。其实，我只对Java感到舒服，所以我为什么问。这不是功课。

可能的重复：link1 link2

来源

2012-01-28 coder_15

你好，投票者，我错了什么？我问的是错误的问题吗？如果可能请解释它 – 2012-01-28 06:51:30

请注意，Java有[按位运算符]（http://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html），所以移植它应该是相当直接的（不是这有助于理解算法）。 – 2012-01-28 07:08:22

可能的重复[帮我理解这个“编程珍珠”bitsort程序]（http://stackoverflow.com/questions/1050253/help-me-understand-this-programming-pearls-bitsort-program） – Borealid 2012-01-29 06:05:32

我们给出的数字会介于0骗N，

我们做一个大的BitSet，这是不可或缺的一大布尔阵列（末尾工作解释），但需要较少的内存（每个位在技术上是一个布尔值）

乔恩做什么，他将设置为false整个位，那么对于遇到的每个号码，他将是位真....最后，他通过运行位集合和他为每个true条目打印索引。这将排序一个数组，我们知道一个元素始终位于0 to N之间。

注意：上述算法将失败，重复。

现在的位掩码的东西...

说我有一个整数阵列（的sizeof（int）的= 32），但我想用它如N大小的布尔数组。那么我真的需要多少元素？这是N/32

int a[1 + N/BITSPERWORD]; // allocates BitSet of N size

现在，如果我要访问的位集合的元素ith这里是如何索引的作品。

例如，i = 49

所以a[0]包含的位0-31，一个[1]包含32-63。

a[i/32]（赋予您int数组元素包含位）和i % 32该元件内的位的位置。

因此对于i= 49,a[49/32] & (1 << (i % 32))会告诉你第49位是否设置。

如果您熟悉按位优化，您知道除以2的因子基本上是将数字右移多个因子。

32 = 2^5 ...因此X/32相同X >> 5

也X % 32是相同X & 0x1f

test如果在该位置位集设置函数给出了1，

clr清除该位置上的位为零

set将位集设置为之一。

唷！希望有所帮助。

来源

2012-01-28 07:52:17 st0le

很好的解释。谢谢@ st0le :) – 2013-04-13 12:57:56

如果我没有记错，使用了一下在这方面设定的是有效地追踪这些整数出现在磁盘上的文件。当传递文件时，整数i的存在通过将数组a的第i位设置为1来指示。

例如，如果a [0] = 5，则二进制值32位（记住BITSPERWORD常量假定代码在32位机器上运行）在[0]处为0 ... 01010。这将表明整数1和3出现在文件中，但整数2以及4到31在文件中未找到。

的主要方法的步骤是：在阵列

将所有的位，一个为0。
扫描该文件，阵列的第i位，设定为1，如果整数，我遇到过。
测试是否在文件中找到整数i，并且它是否将整数打印到屏幕上。

来源

2012-01-28 07:00:15

如何在Java中编写比特排序程序？

回答

相关问题