ビット論理演算を使用してビットベクトルを実現する方法
1476 ワード
ビット論理演算を使用してビットベクトルを実装する方法、およびビットベクトルの設定、クリア、およびテストを実装する方法.
9999999999サイズのビットを追加し、int配列で値を表す場合は9999999999サイズが必要です.しかし、int型ごとに32を表すと、
99999999/32=312499余1なので、メモリを節約できます.ビットでしか表示できないので、まず以下の点がわかります
<1>mを2^nで割ると商はm<<2>mを2^nで割った残数をm&(2^n-1)と表す
<3>int型変数aのk番目の位置1、すなわちa=a|(1<<4>int型変数aのk番目を0にクリアする、すなわちa=a&~(1
いくつかの説明:
i<より多くの演算の応用については、私の別の文章を参照してください.
9999999999サイズのビットを追加し、int配列で値を表す場合は9999999999サイズが必要です.しかし、int型ごとに32を表すと、
99999999/32=312499余1なので、メモリを節約できます.ビットでしか表示できないので、まず以下の点がわかります
<1>mを2^nで割ると商はm<
<3>int型変数aのk番目の位置1、すなわちa=a|(1<
#include "stdafx.h"
#include<iostream>
#define BITSPERWORD 32// ,Int 32
#define MASK 0x1F//2^5-1,
#define SHIFT 5//
#define N 10000000
using namespace std;
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 _tmain(int argc, _TCHAR* argv[])
{
set(999);
if(test(999))
cout<<"true"<<endl;
else
cout<<"false"<<endl;
clr(999);
if(test(999))
cout<<":true"<<endl;
else
cout<<"false"<<endl;
return 0;
}
いくつかの説明:
i<