ビット論理演算を使用してビットベクトルを実現する方法

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#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<より多くの演算の応用については、私の別の文章を参照してください.