如何在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中編寫比特排序程序？

回答

相關問題