이“프로그래밍 펄스”비트 소트 프로그램을 이해하도록 도와주세요.

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

  •  20-08-2019
  •  | 
  •  

문제

Jon Bentley는 그의 책 프로그래밍 진주의 1 열에서 비트 벡터를 사용하여 0이 아닌 양의 정수를 분류하는 기술을 소개합니다.

나는 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 및 테스트 기능이 수행하는 기능을 이해하고 아래를 설명하고 다음을 설명합니다.

  • CLR은 ITH 비트를 지 웁니다
  • 세트는 ITH 비트를 설정합니다
  • 테스트는 ith 비트에서 값을 반환합니다

이제 나는 기능이 어떻게하는지 이해하지 못합니다. 이 세 가지 기능에서 발생하는 모든 비트 조작을 파악할 수 없습니다.

도와주세요.

도움이 되었습니까?

해결책

처음 3 개의 상수는 상호 관련이 있습니다. Bitsperword는 32입니다. 컴파일러+아키텍처를 기반으로 설정하고 싶습니다. 2^5 = 32 때문에 시프트는 5입니다. 마지막으로 마스크는 0x1F이며 이진에서 11111입니다 (즉 : 하단 5 비트는 모두 설정 됨). 동등하게, mask = bitsperword -1.

비트셋은 개념적으로 비트 배열 일뿐입니다. 이 구현은 실제로 INT 배열을 사용하며 int 당 32 비트를 가정합니다. 따라서 조금 설정, 명확 또는 테스트를 원할 때마다 두 가지를 알아 내야합니다.

  • 어떤 int (배열)
  • 우리가 말하는 int의 비트 중 어느 것이

우리는 INT 당 32 비트를 가정하기 때문에 원하는 배열 인덱스를 얻기 위해 32 (및 Truncate)로 나눌 수 있습니다. 32 (Bitsperword)로 나누는 것은 오른쪽으로 5 (Shift)로 이동하는 것과 동일합니다. 이것이 바로 [i >> Shift] 비트에 관한 것입니다. 이것을 [i/bitsperword]로 쓸 수도 있습니다 (실제로 컴파일러에 합리적인 최적화기가 있다고 가정 할 때 동일하거나 매우 유사한 코드를 얻을 수 있습니다).

이제 우리가 원하는 요소를 알았으므로 어떤 비트를 파악해야합니다. 실제로, 우리는 나머지를 원합니다. 우리는 i%bitsperword 로이 작업을 수행 할 수 있지만 I & Mask가 동일하다는 것이 밝혀졌습니다. Bitsperword는 2 (이 경우 2^5)의 힘이고 마스크는 바닥 5 비트 모두 세트이기 때문입니다.

다른 팁

기본적으로 버킷 정렬 최적화입니다.

  • 길이 n 비트의 약간 배열을 예약하십시오.
  • 비트 배열을 지우십시오 (메인에서는 먼저).
  • 항목을 하나씩 읽으십시오 (모두 뚜렷해야합니다).
    • 읽기 번호가 i 인 경우 비트 배열에서 I'th 비트를 설정하십시오.
  • 비트 배열을 반복하십시오.
    • 비트가 설정되면 위치를 인쇄하십시오.

또는 다시 말해서 (n <10의 경우, 3 숫자 4, 6, 2) 0

빈 10 비트 배열로 시작합니다 (일명 One Integer 일반적으로)

0000000000

4를 읽고 배열에서 비트를 설정하십시오.

0000100000

6을 읽고 배열에서 비트를 설정하십시오

0000101000

2를 읽고 배열에서 비트를 설정하십시오

0010101000

배열을 반복하고 비트가 하나로 설정된 모든 위치를 인쇄하십시오.

2, 4, 6

정렬.

set ()로 시작하여 :
5의 오른쪽 이동은 32로 나누는 것과 동일합니다.
마스크는 0x1f 또는 31입니다. 주소와 함께 int는 int 내에서 비트 인덱스를 제공합니다. 주소를 32로 나누는 나머지 부분과 동일합니다.
비트 인덱스 ( "1 << (i & mask)")에 의해 남겨진 1 변속은 주어진 위치 세트에서 단 1 비트를 갖는 정수를 초래합니다.
oring은 비트를 설정합니다.
라인 "int sh = i >> shift;" 그들은 낭비 된 선입니다. 그들은 그 아래에 다시 sh를 사용하지 않았고 대신 "i >> shift"를 반복했습니다.

clr ()는 기본적으로 1 << (i & mask)로 켜기는 대신 비트를 설정하기 위해 비트를 제거하기 위해 반전을 설정하는 것을 제외하고는 세트와 동일합니다. 비트를 테스트하기 위해 1 << (i & mask)가있는 test () 및

Bitsort는 또한 목록에서 중복을 제거합니다. 정수 당 최대 1 명만 계산하기 때문입니다. 비트 대신 정수를 사용하여 각각 1 개 이상을 계산하는 종류를 라디습니다.

비트 마법은 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'TH 비트를 설정하려면 다음을 수행 할 수 있습니다.

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

추가 Gotcha는 모듈로 연산자를 논리적으로 대체 할 수 있고, 두 번째 피연산자가 2의 전력이라면 / 연산자도 교대로 대체 될 수 있다는 것입니다.

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

이것은 궁극적으로 매우 조밀하면서도 indepher-the-bitfucker-agromostic에 대한 지연으로 요약됩니다.

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

그러나 나는 알고리즘이 단어 당 40 비트에 대해 작동하는 것을 보지 못한다.

DDJ의 Bentleys의 원본 기사에서 발췌 한 내용을 인용하면 코드가 높은 수준에서 수행하는 것입니다.

/* 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. 0000000에서 999999의 키와 비트의 존재/부재에 따라 0 또는 1 값이있는 해시 맵을 만들어 Java로이를 수행 할 수 있습니까? 그러한 프로그램에 대한 의미는 무엇입니까?

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top