ビット操作

質問

「ビット操作を用いて素数を調べたい」です。

　unsigned 型の配列bit[16]を用いてビット操作によって素数を調べたいのですが、
　例えば、bit[0]からbit[1]への移動方法？を教えてください。

回答No.2

noname#30727 · ベストアンサー

「エラトステネスのふるい」をビット配列でという事なのかな？

unsigned bit[16]; /* unsigned は 32 ビットだとする */

void set_bit(int n)
{
bit[n / 32] |= 1 << (n % 32);
}

unsigned get_bit(int n)
{
return bit[n / 32] & (1 << (n % 32)); /* 戻り値は 0 か 0 以外で判定 */
}

というような感じでしょうか。

お礼

「エラトステネスのふるい」をビット配列でという事ということです。
参考にさせてもらいます。

補足

ありがとうございました。
　ちゃんとできました

回答No.3

takebou

#1のものです。
エラトステネスのふるいですか。こういう方法もあるんですねぇ。
無知でした。ごめんなさい。

補足

ありがとうございました。
　ちゃんとできました。

回答No.1

takebou

ビット操作で素数？
素数って2,3,5,7,11,13・・・という数ですよね？
で、それをビット操作で求めるのは無理なんじゃないかと思います。

ビット操作をするのなら、配列を使わずに、unsignedの変数1つでやったほうが楽ですよ。
unsigned bit;
bit=1;
bit=bit<<1;
でビット0の'1'がビット1にシフトされます。

補足

アドバイスありがとうございます。
　とり合えず自分なりの考え方を書いてみました。
　実際はunsigned型の配列を用いるらしいです。

　例えばkenchiが32ｂｉｔであるとして考えてみました。
　これを配列を用いて500までの素数を求めたいんです。
　コンパイルしてないんで（家では出来ないんで）うごくかどうか、分かりませんが、配列を使うとするとどうなるのでしょうか。。

kenchi=1;
for(i=2;i<=32;++i)　　このループで32までの素数を求めています。
{
for(sosuu=1,j=2;j<=i;++j)　　
{
k=1<<j;
if(k&kenchi)　kenchiに１が入っていたら素数なので
{　　　　　　　
if(i%j) sosuu*=1;その数で割って余りがでなければ１をかけて
else sosuu=0;　　　0なら０をかえします　
}
}　　そうすると素数ならsosuuは１となります。
if(sosuu) 　そのときは1つ先のbitを１にします。
{
l=1<<i;
kenchi|=l;
}
}
}