ビットでフラグ管理

[L'z]

とても多くのフラグを管理する必要ができました。
フラグは１か０のどちらかなのでint型ではなくビットで管理しようと思います。

下のコードがビットで管理する方法として思いついたものをかいたものです。
例でフラグの数を10万としています。
writeはフラグxを1にしてreadはフラグxを表示します。

コード:

// 宣言
char bit[12500]; // char型は１バイト（８ビット）なので÷８の値

// write
// xはフラグの番号
int i = x / 8;
int j = x % 8;
int w = 1;
w <<= j;
bit[i] |= w;
	
// read
// xはフラグの番号
int i = x / 8;
int j = x % 8;
int flag = 1;
flag <<= j;
flag &= bit[i];
flag = flag?1:0;
cout << x << " : " << flag << endl;

xにいくつかの値を入れて試したところ一応動いたのですが、このような方法を使ったことがなく問題ないか心配なので確認をお願いしたいです。
xは0からフラグの最大値(この場合は10万)までしか来ないようになっています。

また、このフラグをまとめて保存するときはchar bit[12500]を文字列としてファイル出力、読み込むときも文字列として読み込みで可能ですか？
char型は１バイトであり文字列として書きこめばバイトオーダーは問題ないと思うのですがビットが文字として存在しない値になった場合もビットは正しく保存できるのかがわかりません。
確認するにもマルチバイト文字にして日本語も可能になると文字が存在しない値がアスキーコードをみてもわからず試せません。

[nil]

http://www.geocities.jp/ky_webid/cpp/library/008.html
こんなものがあったような……

あとchar型配列は文字列として出力すると考えずに
普通に数値として出力すればいいのでは……?

[beatle]

C言語ではchar型は8ビットとは限りませんが（言い換えると1バイトは8ビットとは限りませんが）、そのあたりの話は勉強されてますか？
それから、charのような有符号整数型に対するビット演算は処理系定義ですので、要確認です。
以上の細かい話を除けば、readとwriteの処理は間違っていないように見えます。

unsigned char型の配列で1フラグ1バイトで管理しても、そんなにメモリは食いませんし、頑張ってビットでやるよりも単純でいいかもしれません。たとえ100万個のフラグを配列で管理しても、使用メモリは1MBです。
unsigned charの配列なら、将来フラグが1,0ではなくて複数の値を取りたくなったときにも、楽に対応できますしね。

[バグ]

ビットフィールドを使用するのもいいかもしれませんね。
下記のソースは、unsigned charのサイズが8ビットである環境なら動くと思います。

コード:

#include <stdio.h>

union BIT8
{
	unsigned char BYTE;
	struct
	{
		unsigned char B0 : 1;
		unsigned char B1 : 1;
		unsigned char B2 : 1;
		unsigned char B3 : 1;
		unsigned char B4 : 1;
		unsigned char B5 : 1;
		unsigned char B6 : 1;
		unsigned char B7 : 1;
	};
};

int main(void)
{
	union BIT8 bit;

	bit.BYTE = 0x00;
	bit.B1 = 1;
	bit.B3 = 1;
	bit.B5 = 1;
	bit.B7 = 1;

	printf("%u\n", bit.BYTE);
	printf("%u,%u,%u,%u,%u,%u,%u,%u\n", bit.B7, bit.B6, bit.B5, bit.B4, bit.B3, bit.B2, bit.B1, bit.B0);
	return 0;
}

[softya（ソフト屋)]

とても多くのフラグといっても定義を見る限りは１０万個程度のようです。
１バイトのフラグで管理しても１００ＫＢも必要ありませんので本当に必要なものかよく考えてみて下さい。
８ビットから１６ビットパソコンの時代ならともかく現代でビットでフラグ管理が必要な状況が思い浮かびません。

ビット化はメモリ効率はアップしますが、L'zさんが気にしていたスピード効率の面では最悪です。
あとデバッグ効率も悪くなります。

[L'z]

http://www.geocities.jp/ky_webid/cpp/library/008.html
こんなものがあったような……

あとchar型配列は文字列として出力すると考えずに
普通に数値として出力すればいいのでは……?

bitsetはそういうものがあるのは知っていましたが使ったことがなかったのですぐに書けるコードにしました。
bitsetにする利点は速度ですか？
バイナリ出力でもいいですが、文字列としてでもできるのか気になりました。

C言語ではchar型は8ビットとは限りませんが（言い換えると1バイトは8ビットとは限りませんが）、そのあたりの話は勉強されてますか？
それから、charのような有符号整数型に対するビット演算は処理系定義ですので、要確認です。
以上の細かい話を除けば、readとwriteの処理は間違っていないように見えます。

unsigned char型の配列で1フラグ1バイトで管理しても、そんなにメモリは食いませんし、頑張ってビットでやるよりも単純でいいかもしれません。たとえ100万個のフラグを配列で管理しても、使用メモリは1MBです。
unsigned charの配列なら、将来フラグが1,0ではなくて複数の値を取りたくなったときにも、楽に対応できますしね。

1バイト8ビットでないというのは知りませんでした。
普通のPCは8で特殊なコンピュータなどが4ですか？
Windowsのソフトとしてexeファイルにする以上8でいいと思うのですが良く無いですか？
ビット演算なら符号のありなしは関係ないと思ってました。unsigned char にすれば問題ないですよね。

unsigned charにフラグを入れればint型の4分の1で済みますね。しかし今回は拡張予定もなくファイル保存時に容量を減らすことが目的だったのでビットを選びました。ここまでフラグが多いのもめったにないと思うので以後フラグ管理のときunsigned charにしようかと思います。

ビットフィールドを使用するのもいいかもしれませんね。
下記のソースは、unsigned charのサイズが8ビットである環境なら動くと思います。

コード:

#include <stdio.h>

union BIT8
{
	unsigned char BYTE;
	struct
	{
		unsigned char B0 : 1;
		unsigned char B1 : 1;
		unsigned char B2 : 1;
		unsigned char B3 : 1;
		unsigned char B4 : 1;
		unsigned char B5 : 1;
		unsigned char B6 : 1;
		unsigned char B7 : 1;
	};
};

int main(void)
{
	union BIT8 bit;

	bit.BYTE = 0x00;
	bit.B1 = 1;
	bit.B3 = 1;
	bit.B5 = 1;
	bit.B7 = 1;

	printf("%u\n", bit.BYTE);
	printf("%u,%u,%u,%u,%u,%u,%u,%u\n", bit.B7, bit.B6, bit.B5, bit.B4, bit.B3, bit.B2, bit.B1, bit.B0);
	return 0;
}

コードありがとうございます。
この方法も利点は速度ですか？

とても多くのフラグといっても定義を見る限りは１０万個程度のようです。
１バイトのフラグで管理しても１００ＫＢも必要ありませんので本当に必要なものかよく考えてみて下さい。
８ビットから１６ビットパソコンの時代ならともかく現代でビットでフラグ管理が必要な状況が思い浮かびません。

ビット化はメモリ効率はアップしますが、L'zさんが気にしていたスピード効率の面では最悪です。
あとデバッグ効率も悪くなります。

例なので10万程度にしましたが最大でINT_MAXの値まで必要かもしれません。
最大までいかなくてもメガは確実に行くかと思います。
実行中はそれでもいいのですがそのデータを保存するときにメガ、場合によってはギガ?も使うならできるだけ減らしたいと思いビットの方法にしました。
1か0なので実行中はunsigned charで保存時は圧縮するというのも考えましたが圧縮は方法を知らなかったのですぐ書ける方法としてビットの方法にしました。

[softya（ソフト屋)]

例なので10万程度にしましたが最大でINT_MAXの値まで必要かもしれません。
最大までいかなくてもメガは確実に行くかと思います。
実行中はそれでもいいのですがそのデータを保存するときにメガ、場合によってはギガ?も使うならできるだけ減らしたいと思いビットの方法にしました。
1か0なので実行中はunsigned charで保存時は圧縮するというのも考えましたが圧縮は方法を知らなかったのですぐ書ける方法としてビットの方法にしました。

参考にどの様な場面で使うかお聞きしてよいでしょうか？
INT_MAXまで使うなど尋常な話ではありません。
ゲームとしてはアクセスを考えると速度的にゲームにならない可能性もあります。
そもそも設計的にまずい気がするんですが。

[L'z]

例なので10万程度にしましたが最大でINT_MAXの値まで必要かもしれません。
最大までいかなくてもメガは確実に行くかと思います。
実行中はそれでもいいのですがそのデータを保存するときにメガ、場合によってはギガ?も使うならできるだけ減らしたいと思いビットの方法にしました。
1か0なので実行中はunsigned charで保存時は圧縮するというのも考えましたが圧縮は方法を知らなかったのですぐ書ける方法としてビットの方法にしました。

参考にどの様な場面で使うかお聞きしてよいでしょうか？
INT_MAXまで使うなど尋常な話ではありません。
ゲームとしてはアクセスを考えると速度的にゲームにならない可能性もあります。
そもそも設計的にまずい気がするんですが。

今回は前回のゲームとは異なります。
それに毎フレームアクセスするわけではないので速度はそこまできにしてません。

乱数をとってきてその値を利用して色々とするわけです。
その値で２度と同じものが発生しないようにしています。
そのためフラグもたてるだけで０に戻すことは無いです。
INT_MAXまでする必要もないといえばないですがとりあえずできるかぎり多くしたいわけです。

[softya（ソフト屋)]

乱数をとってきてその値を利用して色々とするわけです。
その値で２度と同じものが発生しないようにしています。
そのためフラグもたてるだけで０に戻すことは無いです。
INT_MAXまでする必要もないといえばないですがとりあえずできるかぎり多くしたいわけです。

なるほど。
もし配布するゲームでメモリが100MBを超えるようなら仮想記憶が働いて動きが悪くなるＰＣが出てくる可能性は考えておいたほうが良いでしょう。
ビット化したとしても500MB(INT_MAX)なら多くのＰＣでは実メモリが足りずに仮想記憶が働いてしまうと思ったほうが良いです。
それだけは頭に入れておいて下さい。

[補足]
ちなみにメモリアクセス効率重視ならビットを使うにしてもunsigned int型をお勧めします。

[みけCAT]

最初に（使う最小値）～（使う最大値）までの整数を列挙してそれをシャッフルしておき、
使用する際はそれを前から順番に使用する、という方法もあります。
ただし、メモリを大量に使う（0～INT_MAXの場合、int型が4バイトだとすると約16GB）ので、注意してください。
シャッフルのしかたはこのトピックを参考にしてください。

[softya（ソフト屋)]

現実問題としてINT_MAXまでの乱数値を扱うとして、一定期間内に１万個程度のユニークな数字で良いのであれば数値のまま貯めこんでハッシュ探索するとかアルゴリズムを工夫する余地はあります。
本当にビット化して数百ＭＢもの配列が必要なのでしょうか？その情報はどれだけの期間、どれだけの数のユニークな乱数値を貯めこむ必要があるのでしょうか？

[ISLe]

INT_MAX個の乱数って、32ビット環境だとして、1ミリ秒に1つずつでも全部消費するのに25日弱かかりますけど。

同じ値を二度使いたくない理由は何でしょうね。
後になるほど予測しやすくなってしまいますけど。
同じ擬似乱数発生系列を使うのではダメなことなんでしょうかね。

[L'z]

もし配布するゲームでメモリが100MBを超えるようなら仮想記憶が働いて動きが悪くなるＰＣが出てくる可能性は考えておいたほうが良いでしょう。
ビット化したとしても500MB(INT_MAX)なら多くのＰＣでは実メモリが足りずに仮想記憶が働いてしまうと思ったほうが良いです。
それだけは頭に入れておいて下さい。

わかりました。

ちなみにメモリアクセス効率重視ならビットを使うにしてもunsigned int型をお勧めします。

unsigned char より unsigned int のほうがいいのですね。
前に、大きな値を使わないからといってshortやcharにしても演算時にはint型にして計算されるから無駄 というのを聞いたことがあります。
そういうことなのですか？

最初に（使う最小値）～（使う最大値）までの整数を列挙してそれをシャッフルしておき、
使用する際はそれを前から順番に使用する、という方法もあります。
ただし、メモリを大量に使う（0～INT_MAXの場合、int型が4バイトだとすると約16GB）ので、注意してください。
シャッフルのしかたはこのトピックを参考にしてください。

シャッフルの方法は別の場所で使ってます。
この場合はみけCATさんの注意に書かれているようすごくメモリを使うため使っていません。

現実問題としてINT_MAXまでの乱数値を扱うとして、一定期間内に１万個程度のユニークな数字で良いのであれば数値のまま貯めこんでハッシュ探索するとかアルゴリズムを工夫する余地はあります。
本当にビット化して数百ＭＢもの配列が必要なのでしょうか？その情報はどれだけの期間、どれだけの数のユニークな乱数値を貯めこむ必要があるのでしょうか？

最初は、１回のソフト起動中のみ保存しておくつもりで、使った数値を保存するだけでよかったのですが、せっかくなら使ったものを保存しておきソフトを何度起動しても同じパターンは内容にしようと思ったのです。

INT_MAX個の乱数って、32ビット環境だとして、1ミリ秒に1つずつでも全部消費するのに25日弱かかりますけど。

同じ値を二度使いたくない理由は何でしょうね。
後になるほど予測しやすくなってしまいますけど。
同じ擬似乱数発生系列を使うのではダメなことなんでしょうかね。

最後まで使うことは全く考えてません。ほぼ確実に無理です。
１万～１０万程度でもいいといえばいいのです。
しかしそれだと値が１０００万のときのパターンなどがなくなってしまうので、多くしたいなと思ったわけです。
毎回違うようにしたいというのはただのこだわりです。

[softya（ソフト屋)]

話を総合すると
・ビット化した情報を持つINT_MAX個の配列である必要は全くない。なぜならINT_MAX回数行うわけではないから。
・１０万個程度のINT_MAXまでの値を保持できて毎回違う数字が出れば良い。１０万回後には同じ数字が出ても良い。
・毎フレーム数値を作り出す必要はない。
って事でしょうか。

なのであれば値を保持するツリーやハッシュテーブルで値の同一チェックをすればINT_MAX個の情報ビットは必要ないと思います。
メモリも１０万個ですから４バイトｘ１０万で390KB程度です。これに探査キーやリスト構造を付け加えても１０倍程度で４MBほどで済むのでは無いですか？

[補足]
ISLeさんの「同じ擬似乱数発生系列を使うのではダメなことなんでしょうかね。」と言うのも方法です。
乱数シードをセーブして持ちまわれば同じ数値が出ない事が保証されている乱数生成ルーチンを使う方法ってことですね。
これなら乱数シードだけですので非常にコンパクトです。

[L'z]

話を総合すると
・ビット化した情報を持つINT_MAX個の配列である必要は全くない。なぜならINT_MAX回数行うわけではないから。
・１０万個程度のINT_MAXまでの値を保持できて毎回違う数字が出れば良い。１０万回後には同じ数字が出ても良い。
・毎フレーム数値を作り出す必要はない。
って事でしょうか。

なのであれば値を保持するツリーやハッシュテーブルで値の同一チェックをすればINT_MAX個の情報ビットは必要ないと思います。
メモリも１０万個ですから４バイトｘ１０万で390KB程度です。これに探査キーやリスト構造を付け加えても１０倍程度で４MBほどで済むのでは無いですか？

そうですね。デバッグ用として値を入力も可能にしていたので１から続いている必要があると思ってましたが、よく考えると何が入力あっても問題ないですね。
現時点で最初に書いた方法である程度実装しているので修正するか検討します。
修正する場合で何かわからない部分があればまた質問するつもりなのでよろしくおねがいします。

[補足]
ISLeさんの「同じ擬似乱数発生系列を使うのではダメなことなんでしょうかね。」と言うのも方法です。
乱数シードをセーブして持ちまわれば同じ数値が出ない事が保証されている乱数生成ルーチンを使う方法ってことですね。
これなら乱数シードだけですので非常にコンパクトです。

擬似乱数はすべての数が出る前に同じ数が出る場合もあると思っていましたがそんなことはないのですね。
RAND_MAXは32767(0x7fff)なのでINT_MAXまでの値を出すには乱数をdouble型にキャストしてRAND_MAXで割ってINT_MAXを掛けることで、ソフトを終了しても続きを出すにはランダムを取り出した数を保存して次回の起動時にその分を捨てればできますね。32768種類とすこし少なくなりますけど。

修正するならこちらのほうが楽そうですね。

[L'z]

最初の質問の回答は得られたので解決マークつけておきます。

私が ？ と書いた部分で回答がないとこもあったのでまだ返信あるかもと思い少しまってみたのですがなかったので。


少し忙しく、プログラム修正した場合に質問があったとしてもこのトピックは流れてしまってると思うので、そのときは新しく立てると思います。