Java에서 비트 정렬 프로그램을 작성하는 방법은 무엇입니까?

Question

안녕하세요. Bentley의 고전 프로그래밍 진주에있는 bitsort 프로그램을 이해하는 데 문제가 있습니다. Bitmask와 Bitset을 처음 사용하기 때문에 이러한 개념을 이해할 수 없습니다. 사실이 프로그램은 그래서 아래에. "어떻게 디스크 파일을 정렬하는?"입니다 어떤 사람이 나에게이 코드를 설명해 주시겠습니까 코드

#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만으로 편안하므로 왜 내가 묻고있다. 숙제가 아닙니다.

가능한 중복 : link1link2

Answer 1

우리는 숫자가

그래서 우리가 (마지막에 설명 워킹) 큰 부울 배열 필수적인 대형 BitSet을 확인 N 0 사이에 거짓말을하려고 제공하지만, 적은 메모리를 소요하고

그래서 Jon은 전체 비트를 false으로 설정 한 다음 마주 치게되는 숫자마다 비트를 true로 설정합니다. 마지막으로 그는 비트 세트를 실행하고 각 true 항목에 대해 그는 색인을 인쇄합니다. 요소가 항상 0 to N 사이에있는 것을 알 수있는 배열을 정렬합니다.

참고 : 위의 알고리즘은 중복되어 실패합니다. 비트 마스크 물건에 대한 지금

...

내가 정수 배열 (는 sizeof (int)를 = 32)가 말하지만 난 N 크기의 부울 배열처럼 사용하고 싶습니다. 그렇다면 정말 필요한 요소는 몇 개입니까? 나는 비트 세트의 ith 요소에 액세스 할 경우 여기 인덱싱 작업이 방법은 이제 N/32

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

을합니다.

예는

i = 49 정도로 a[0]는 [1]이 포함 32-63, 0-31 비트를 포함.

a[i/32]는 i % 32 및 그 요소 내의 비트 위치 ( 소자가 비트를 포함하는 int 배열하면 준다).

i= 49의 경우 a[49/32] & (1 << (i % 32))은 49 번째 비트가 설정되어 있는지 여부를 알려줍니다.

비트 최적화에 익숙하다면 2로 나누는 것이 본질적으로 요소 수만큼 오른쪽으로 이동한다는 것을 알고 있습니다. 위치에서의 비트 세트가 설정된 경우 함수 (1)를 제공

testX & 0x1f로

32 = 2^5 ... 따라서 X/32 동일한 X >> 5

으로서도 X % 32는 동일

clr 그 위치의 비트 셋을 제로로 클리어한다

set은 비트 세트를 그 위치에 설정한다. 하나.

피어! 희망이 도움이됩니다.

Answer 2

내가 정확히 기억한다면,이 맥락에서 설정된 비트의 사용이 효율적으로 디스크 파일에 나타나는 정수를 추적하는 것입니다. 파일을 넘어갈 때 정수 a의 존재는 배열 a의 i 번째 비트를 1로 설정하여 나타냅니다.

예를 들어, [0] = 5이면 이진 값은 a [0]이 0 ... 01010 일 때 32 비트 (BITSPERWORD 상수는 코드가 32 비트 시스템에서 실행된다고 가정합니다). 이것은 정수 1과 3이 파일에 있지만 정수 2와 4 - 31이 파일에서 발견되지 않았 음을 나타냅니다. 주요 방법

단계는 : 배열

1. 세트의 모든 비트, A, 0
2. 정수의 경우, (1) 배열의 i 번째 비트를 설정하여 파일을 검색하려면 나는 만난다.
3. 파일에 정수 i가 있는지 테스트하고 화면에 정수 을 인쇄했는지 테스트합니다.