位向量

位向量：就是使用位逻辑运算实现位向量中指定位的设置，清零，探测。

下面代码是编程珠玑上的实现.

#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)); }

要把a想像成一个二维数组就好理解了。

下面一个简单的用法

#include <iostream>

using namespace std;

int a[10] = {0};

const int shift = 5;
const int maskl = 0x1F;
void setB(int i)
{
 a[i>>shift] |=1<<(i&maskl);
}
void cls(int i)
{
 a[i>>shift] &=~(1<<(i&maskl));
}
int test(int i)
{
 return a[i>>shift] &(1<<(i&maskl));
}
int main()
{
 int num[] = {1,2,3,5,6,4,7,8,9};

 cout<<a[0]<<"   a[0]"<<endl;
 for (int i=0;i<9;i++)
 {
  setB(num[i]);
  cout<<num[i]<<endl;

  cout<<a[0]<<"   a[0]"<<endl;
 }
 for (int i=0;i<9;i++)

 {
  if (test(num[i]))
  {
   cout<<num[i]<<" is set"<<endl;
  }
  else
  {
   cout<<num[i]<<"is not set"<<endl;
   cout<<a[0]<<endl;
  }
 }
 system("pause");
}