ビット論理演算を使用してビットベクトルを実現する
1882 ワード
ビット論理演算を使用してビットベクトルを実現するにはどうすればいいですか?
最初、この問題を見て、私も少し愚かで、ビット論理演算はまだ少し理解していますが、ビットベクトルという名詞はまだ少しよく知られていません.
したがって,この問題を解決するには,ビット論理演算とビットベクトルの2つの概念を明確にしなければならない.
1.ビット演算:&(ビットと)、|(ビットまたは)、>>と<>>(cにはなくjavaにはあります).
ビット演算はビットベクトルを実現するために主に最初の3つのビット演算を用いる.
2.ビットベクトル:その名の通り、ビットベクトルはいくつかのバイナリビットからなるベクトルである.多くの場合、オブジェクトをバイナリで表すことができます.しかし、1つのビット(単独のビットからなるデータ型は存在しない)を1つの変数名で直接表すことはできません.したがって、複数のビットを基本的なデータ型に構成し、この基本的なデータ型を操作することで、ビットを操作する目的を達成することができます.また,便宜上,ビットからなる基本データ型を配列することで,一定範囲のビットデータ集合を操作できる.
3.ビットベクトルをどのように操作するか:ビットベクトルの皆さんの操作は直接名前でアクセスすることはできません.位置でしか操作できません.つまり、数桁目を操作します.我々から見れば、ビットは0−n連続であり、実際には、これらのビットは異なる配列要素に存在し、異なる配列の異なる位置に分布するため、基本データ型配列で格納される.intタイプを基本データ型とすると、1つのintタイプは32ビット(c++)を格納することができる.特定のビット(pos)については、まずどの配列にあるか(pos/32)を求め、その後、この配列におけるビットの特定の位置(pos%32)を求める.
4.ビットに対する具体的な操作は三つある:特定の位置1に対して、特定の位置0に対して、特定の位置を判断する.
5.ビットを操作するには、次のいくつかの表示を理解します.
①m/(2^n) = m>>n;
②m%(2^n) = ( m & 2^(n)-1 );
③int型変数aのk番目の位置1:a=(a|(1<④int型変数aのk位を0:a=(a&~(1<
6.実装コード
7.******
最初、この問題を見て、私も少し愚かで、ビット論理演算はまだ少し理解していますが、ビットベクトルという名詞はまだ少しよく知られていません.
したがって,この問題を解決するには,ビット論理演算とビットベクトルの2つの概念を明確にしなければならない.
1.ビット演算:&(ビットと)、|(ビットまたは)、>>と<>>(cにはなくjavaにはあります).
ビット演算はビットベクトルを実現するために主に最初の3つのビット演算を用いる.
2.ビットベクトル:その名の通り、ビットベクトルはいくつかのバイナリビットからなるベクトルである.多くの場合、オブジェクトをバイナリで表すことができます.しかし、1つのビット(単独のビットからなるデータ型は存在しない)を1つの変数名で直接表すことはできません.したがって、複数のビットを基本的なデータ型に構成し、この基本的なデータ型を操作することで、ビットを操作する目的を達成することができます.また,便宜上,ビットからなる基本データ型を配列することで,一定範囲のビットデータ集合を操作できる.
3.ビットベクトルをどのように操作するか:ビットベクトルの皆さんの操作は直接名前でアクセスすることはできません.位置でしか操作できません.つまり、数桁目を操作します.我々から見れば、ビットは0−n連続であり、実際には、これらのビットは異なる配列要素に存在し、異なる配列の異なる位置に分布するため、基本データ型配列で格納される.intタイプを基本データ型とすると、1つのintタイプは32ビット(c++)を格納することができる.特定のビット(pos)については、まずどの配列にあるか(pos/32)を求め、その後、この配列におけるビットの特定の位置(pos%32)を求める.
4.ビットに対する具体的な操作は三つある:特定の位置1に対して、特定の位置0に対して、特定の位置を判断する.
5.ビットを操作するには、次のいくつかの表示を理解します.
①m/(2^n) = m>>n;
②m%(2^n) = ( m & 2^(n)-1 );
③int型変数aのk番目の位置1:a=(a|(1<
6.実装コード
#include
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F//2^5-1
#define N 10000000
int a[1 + N/BITSPERWORD];
// i 1
void set( int i)
{
a[ i >> SHIFT] = ( a[ i >> SHIFT] | (1 << (i & MASK)));
}
// i 0
void clr( int i)
{
a[ i >> SHIFT] = ( a[ i >> SHIFT] & ~(1 << (i & MASK)));
}
//
int test( int i)
{
return a[ i >> SHIFT] & ( 1 << (i & MASK));
}
int main()
{
set(1001);
if( test(1001))
{
printf("true %d
",test(1001));
}
else
printf("false
");
clr(1001);
if( test(1001))
printf("true
");
else
printf("false
");
return 0;
}
7.******