かっこ"プログラミングの真珠"bitsortプログラム

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

  •  20-08-2019
  •  | 
  •  

質問

Jonベントレー、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を解除に伴ビット
  • 設定セットの各ビット
  • 試験値を返しますので、各ビット

現在、わかりませんどのように機能をいうことになったと言われています。ができない図のビット操作に起きていることその機能

を参考にしてください。

役に立ちましたか？

解決

最初の3つの定数に関係し合っています。BITSPERWORDは32.このまえにしたい設定に基づくコンパイラ+ます。シフトは5日で2^5=32.最後に、マスクを0x1Fる11111バイナリ(ie:下の5つのビットはすべての通知非通知を設定できます。同様に、マスク=BITSPERWORD-1に示します。

のbitsetが概念上での配列ですね。この実装は実際に使用してint値の配列は、は32ビットint.だいたいセット、クリアまたはテストの読み込)ビット必要がありまめには二つのことをやろうとしてい

  • するintの配列)で
  • ることintのビットをしていく

ないと仮定して32ビットintまで分割による32(および切り詰めになりましたが、結果の配列インデックスです。分割による32(BITSPERWORD)と同じ右傾化による5(フリー）そういうのはa[i>>シフト]ビットです。きのように記述することもできますこと[i/BITSPERWORD](実際、いかに同一でも非常に類似コードと仮定してコンパイラは、合理的なオプティマイザ).

今かの要素において、必要がありまれます。うまいります。このことがあり、i%BITSPERWORDが、ここで示されているデータi&マスクは等価です。こBITSPERWORDは2の(2^5この場合は、マスクの下位5のすべてのビットセットです。

他のヒント

基本的にはバケッソの最適化:

  • 予約ビット配列の長さn ビット.
  • のビット配列(第ためのメイン).
  • 読の項目を一つ一つ(なすべて異なる).
    • 設定のi番目のビットのビット配列の場合、読み込み番号です
  • 繰り返し処理を実行し、ビット配列になります。
    • る場合このビットがセットプログラミングインタの位置にします。

すなわち(N < 10ソ3番4人、6人、2)0

始まりは空の10ビット配列(通称一の整数普通)

0000000000

read4セット、ビット配列の..

0000100000

読6のビットの配列

0000101000

read2セットのビットの配列

0010101000

繰り返し配列の印刷位置するビットに設定します。

2, 4, 6

全部エクスペディアで。


：

セット（）で開始 5の右シフトは、それは少しであるint型どの見つけるためにそれを行う32で割ると同じである。
MASKは、アドレスを持つから0x1fまたは31の論理積がint内のビットインデックスを与えています。これは、32
でアドレスを割った余りと同じです 1ビットのインデックス指定された位置のセットにわずか1ビットを有する整数で（「1 <<（I＆MASK）」）の結果だけ左シフトする。
論理和は、ビットをセットします。
ライン "int型のSH = I >> SHIFT;"彼らはその下に再びSHを使用して、代わりにちょうど繰り返し「私>> SHIFT」

なかったので、無駄なラインです

CLR（）は、論理積反転したビットをクリアするために、代わりに1 <<（I＆MASK）との論理和を除いて、基本的にセットと同じであるビットを設定します。試験（1）<<（I＆MASK）との論理積のビットをテストする。

それが唯一の整数につき1までカウントされますので、

bitsortも、リストから重複を削除します。それぞれの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を意味します。

は、行当たり32ビットの1つのワードを使用して、メモリにこれを最適化するときは、列xにおけるビットを使用して設定することができるという事実を得る

int bitrow = 0;
bitrow |= 1 << (x);
我々はビットを反復処理するとき、

さて、私たちは、<全角> HAVE の線形アドレスが、対応する単語を見つける必要があります。

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番目のビットを設定するために、あなたがこれを行うことができます：

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

余分な落とし穴は、モジュロ演算子が論理的に置き換えることができると、第2オペランドが2の累乗である場合/オペレータは、あまりにも、シフトで置き換えることができること、である。

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.私たちは、9999999に0000000からキーとHashMapを作成することによって、Javaでこれを行うことができます    ビットの存在/不在に基づいて、0又は1値？意味は何ですか    このようなプログラムのために？

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top