ビットマップ法の紹介

一、定義ビットマップ法はbitmapの略である.bitmapとは,ある状態を1人ずつ格納し,大規模なデータに適しているが,データ状態はそれほど多くない場合である.通常は、あるデータが存在しないと判断するために使用されます.STLにはビットセット容器がありますが、実はビットマップ法です
データ構造

unsigned int bit[N];

この配列には、N*sizeof(int)*8個のデータを格納できますが、最大数はN*sizeof(int)*8-1のみです.
関連アクション
データの書き込み
配列を定義します:unsigned char bit[8*1024];これにより,8 K*8=64 K個のunsigned shortデータを格納できる.
bit格納バイト位置とビット位置(バイト0~8191、ビット0~7)は、例えば、書き込み1234、バイト順:1234/8=154;ビットシーケンス:1234&0 b 111=2であれば、1234はbitの下付き154バイトに置かれ、そのバイトの2番ビット(0~7)を1にする.

    ： int nBytePos =1234/8 = 154;
   ：   int nBitPos = 1234 & 7 = 2;

     1236 ，
    ： int nBytePos =1236/8 = 154;
   ：   int nBitPos = 1236 & 7 = 4

// /      154     4     1  
val = 1<

コード実装

/* 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  
#define BITSPERWORD 32 
#define SHIFT 5 
#define MASK 0x1F 
#define N 10000000 
int a[1 + N/BITSPERWORD]; 
/*
i int  ，32  ， a int   ，    32      a         ， 32       。
a[i>>SHIFT]  i       int ，  5     2^5   32
(1<>SHIFT] |= (1<>SHIFT] &= ~(1<>SHIFT] & (1<

ビットマップ法を用いて整形配列に重複遍歴配列が存在するか否かを判断し、1つずつbitmapに入れ、bitmapに存在したか否かを検査し、挿入が存在しない場合は重複要素である.