C++ では、true または false を格納するために bool が 1 バイトを必要とするのはなぜですか? (Java も 1 バイトを必要とするのはなぜですか?)
第二に、以下を使用するのはどれくらい安全ですか?
struct Bool {
bool trueOrFalse : 1;
};
第三に、安全だとしても、上記のフィールドテクニックは本当に役に立ちますか? そこでスペースを節約すると聞いたことがありますが、それでもコンパイラがそれらにアクセスするために生成したコードは、プリミティブにアクセスするために生成されたコードよりも大きく、低速です。
bool が true または false を格納するために 1 バイトを必要とするのはなぜですか。1 ビットだけで十分です。
C++ のすべてのオブジェクトは個別にアドレス指定可能でなければならないため* (つまり、オブジェクトへのポインタを持つことができなければなりません)。個々のビットをアドレス指定することはできません (少なくとも従来のハードウェアでは)。
次のものを使用すると、どれくらい安全ですか?
「安全」ですが、あまり効果がありません。
上記のフィールドテクニックは本当に役に立ちますか?
いいえ、上記と同じ理由で ;)
ただし、それらにアクセスするためにコンパイラが生成したコードは、プリミティブにアクセスするために生成されたコードよりも大きく、低速です。
ええそれはそうです。ほとんどのプラットフォームでは、これには含まれるバイト (またはintその他) にアクセスし、ビットシフトとビットマスク操作を実行して関連するビットにアクセスする必要があります。
メモリ使用量が本当に気になる場合は、ビットをパックstd::bitsetする C++ または Java で aを使用できます。BitSet
※一部例外あり。
単一ビットを使用すると、割り当てがはるかに遅くなり、はるかに複雑になります。C/C++ では、1 ビットのアドレスを取得する方法がないため、ビットとして実行することはできません&trueOrFalse。
Java には BitSet と EnumSet があり、どちらもビットマップを使用します。数が非常に少ない場合、大きな違いはないかもしれません。たとえば、オブジェクトは少なくともバイト アラインされている必要があり、HotSpot では 8 バイト アラインされています (C++ では、newオブジェクトは 8 ～ 16 バイトでアラインされている可能性があります)。
少なくとも Java では、キャッシュにうまく収まらない限り、ビットは高速ではありません。
public static void main(String... ignored) {
BitSet bits = new BitSet(4000);
byte[] bytes = new byte[4000];
short[] shorts = new short[4000];
int[] ints = new int[4000];
for (int i = 0; i < 100; i++) {
long bitTime = timeFlip(bits) + timeFlip(bits);
long bytesTime = timeFlip(bytes) + timeFlip(bytes);
long shortsTime = timeFlip(shorts) + timeFlip(shorts);
long intsTime = timeFlip(ints) + timeFlip(ints);
System.out.printf("Flip time bits %.1f ns, bytes %.1f, shorts %.1f, ints %.1f%n",
bitTime / 2.0 / bits.size(), bytesTime / 2.0 / bytes.length,
shortsTime / 2.0 / shorts.length, intsTime / 2.0 / ints.length);
}
}
private static long timeFlip(BitSet bits) {
long start = System.nanoTime();
for (int i = 0, len = bits.size(); i < len; i++)
bits.flip(i);
return System.nanoTime() - start;
}
private static long timeFlip(short[] shorts) {
long start = System.nanoTime();
for (int i = 0, len = shorts.length; i < len; i++)
shorts[i] ^= 1;
return System.nanoTime() - start;
}
private static long timeFlip(byte[] bytes) {
long start = System.nanoTime();
for (int i = 0, len = bytes.length; i < len; i++)
bytes[i] ^= 1;
return System.nanoTime() - start;
}
private static long timeFlip(int[] ints) {
long start = System.nanoTime();
for (int i = 0, len = ints.length; i < len; i++)
ints[i] ^= 1;
return System.nanoTime() - start;
}
版画
Flip time bits 5.0 ns, bytes 0.6, shorts 0.6, ints 0.6
40000 および 400K のサイズの場合
Flip time bits 6.2 ns, bytes 0.7, shorts 0.8, ints 1.1
4Mの場合
Flip time bits 4.1 ns, bytes 0.5, shorts 1.0, ints 2.3
そして40M
Flip time bits 6.2 ns, bytes 0.7, shorts 1.1, ints 2.4
char1 ビットの情報のみを保存する場合、C/C++ でアドレス可能な最小のメモリ単位であるよりもコンパクトなものはありません。(実装によっては、 aは aboolと同じサイズになる場合がありますが、より大きくするcharことができます。)
Acharは C 標準によって少なくとも 8 ビットを保持することが保証されていますが、それ以上のビットで構成することもできます。正確な数は、 (C) または(C++)でCHAR_BIT定義されたマクロを介して入手できます。今日では、これが最も一般的ですが、信頼することはできません (ここを参照)。ただし、POSIX 準拠のシステムおよびWindowsでは 8 であることが保証されています。limits.hclimitsCHAR_BIT == 8
単一のフラグのメモリ フットプリントを削減することはできませんが、複数のフラグを組み合わせることはもちろん可能です。すべてのビット操作を手動で行う以外に、いくつかの代替手段があります。
std::bitsetboost::dynamic_bitset他の人がすでに指摘しているように、いくつかのビットを保存することは常に良い考えではありません. 考えられる欠点は次のとおりです。
char。通常、大量のデータを扱う場合は、メモリとキャッシュへの負担が軽減されるというメリットがあるため、これは理にかなっています。
状態をバイトに保存してみませんか？以下を実際にテストしたことはありませんが、アイデアが得られるはずです。16 または 32 の状態に short または int を使用することもできます。Java の例もあると思います。これを見つけたら投稿します。
__int8 state = 0x0;
bool getState(int bit)
{
return (state & (1 << bit)) != 0x0;
}
void setAllOnline(bool online)
{
state = -online;
}
void reverseState(int bit)
{
state ^= (1 << bit);
}
さて、JAVA版です。それ以来、それを Int 値に格納しました。私の記憶が正しければ、バイトを使用してもとにかく4バイトを使用します。そして、これは明らかに配列として利用されていません。
public class State
{
private int STATE;
public State() {
STATE = 0x0;
}
public State(int previous) {
STATE = previous;
}
/*
* @Usage - Used along side the #setMultiple(int, boolean);
* @Returns the value of a single bit.
*/
public static int valueOf(int bit)
{
return 1 << bit;
}
/*
* @Usage - Used along side the #setMultiple(int, boolean);
* @Returns the value of an array of bits.
*/
public static int valueOf(int... bits)
{
int value = 0x0;
for (int bit : bits)
value |= (1 << bit);
return value;
}
/*
* @Returns the value currently stored or the values of all 32 bits.
*/
public int getValue()
{
return STATE;
}
/*
* @Usage - Turns all bits online or offline.
* @Return - <TRUE> if all states are online. Otherwise <FALSE>.
*/
public boolean setAll(boolean online)
{
STATE = online ? -1 : 0;
return online;
}
/*
* @Usage - sets multiple bits at once to a specific state.
* @Warning - DO NOT SET BITS TO THIS! Use setMultiple(State.valueOf(#), boolean);
* @Return - <TRUE> if states were set to online. Otherwise <FALSE>.
*/
public boolean setMultiple(int value, boolean online)
{
STATE |= value;
if (!online)
STATE ^= value;
return online;
}
/*
* @Usage - sets a single bit to a specific state.
* @Return - <TRUE> if this bit was set to online. Otherwise <FALSE>.
*/
public boolean set(int bit, boolean online)
{
STATE |= (1 << bit);
if(!online)
STATE ^= (1 << bit);
return online;
}
/*
* @return = the new current state of this bit.
* @Usage = Good for situations that are reversed.
*/
public boolean reverse(int bit)
{
return (STATE ^= (1 << bit)) == (1 << bit);
}
/*
* @return = <TRUE> if this bit is online. Otherwise <FALSE>.
*/
public boolean online(int bit)
{
int value = 1 << bit;
return (STATE & value) == value;
}
/*
* @return = a String contains full debug information.
*/
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append("TOTAL VALUE: ");
sb.append(STATE);
for (int i = 0; i < 0x20; i++)
{
sb.append("\nState(");
sb.append(i);
sb.append("): ");
sb.append(online(i));
sb.append(", ValueOf: ");
sb.append(State.valueOf(i));
}
return sb.toString();
}
}
また、これには特別なクラスを実際に使用するべきではなく、変数を使用する可能性が最も高いクラス内に変数を格納する必要があることも指摘しておく必要があります。数百または数千のブール値を持つことを計画している場合は、バイトの配列を検討してください。
たとえば、以下の例。
boolean[] states = new boolean[4096];
以下に変換できます。
int[] states = new int[128];
おそらく、128 配列からインデックス 4095 にアクセスする方法を疑問に思っているでしょう。つまり、単純化すると、これが何をしているのかということになります。4095 は 5 ビット右にシフトされます。これは、技術的には 32 で除算するのと同じです。したがって、4095 / 32 = 切り捨てられます (127)。したがって、配列のインデックス 127 にいます。次に、4095 & 31 を実行して、0 から 31 の間の値にキャストします。これは、2 から 1 を引いた累乗でのみ機能します。たとえば、0,1,3,7,15,31,63,127,255,511,1023 など...
これで、その位置のビットにアクセスできます。ご覧のとおり、これは非常にコンパクトで、ファイル内に 4096 のブール値を持つよりも優れています :) これにより、バイナリ ファイルへの読み書きも大幅に高速化されます。この BitSet が何であるかはわかりませんが、完全なゴミのように見えます。byte、short、int、long は技術的には既にビット形式になっているため、そのまま使用することもできます。次に、メモリから個々のビットにアクセスするための複雑なクラスを作成します。これは、いくつかの投稿を読んで把握できたものです。
boolean getState(int index)
{
return (states[index >> 5] & 1 << (index & 0x1F)) != 0x0;
}
さらに詳しい情報...
基本的に、上記が少しわかりにくい場合は、何が起こっているかを簡略化したバージョンを次に示します。
型「byte」、「short」、「int」、「long」はすべて、異なる範囲を持つデータ型です。
次のリンクを表示できます: http://msdn.microsoft.com/en-us/library/s3f49ktz(v=vs.80).aspx
それぞれのデータ範囲を表示します。
したがって、1 バイトは 8 ビットに相当します。したがって、4 バイトの int は 32 ビットになります。
現在、 N乗に何らかの値を実行する簡単な方法はありません。ただし、ビットシフトのおかげで、ある程度シミュレートできます。1 << N を実行すると、これは 1 * 2^N に等しくなります。したがって、2 << 2^N を実行すると、2 * 2^N を実行することになります。したがって、2 のべき乗を実行するには、常に "1 << N" を実行します。
これで、int が 32 ビットになることがわかったので、各ビットを使用して単純にインデックスを付けることができます。
簡単にするために、「&」演算子を、値に別の値のビットが含まれているかどうかを確認する方法と考えてください。では、値が 31 だったとしましょう。31 になるには、次のビット 0 から 4 を追加する必要があります。これらは 1、2、4、8、および 16 です。これらはすべて合計すると 31 になります。 31 & 16 ビット 4 は 2^4 = 16 であるため、16 が返されます。この値に位置しています。ここで、ビット 2 と 4 がこの値にあるかどうかをチェックする 31 & 20 を実行したとします。ビット 2 と 4 の両方が 2^2 = 4 + 2^4 = 16 = 20 にあるため、これは 20 を返します。ここで、31 と 48 を実行したとしましょう。これはビット 4 と 5 をチェックしています。 31 にビット 5 があります。したがって、これは 16 のみを返します。0 は返しません。したがって、複数のチェックを実行する場合は、物理的にその値と等しいことを確認する必要があります。
以下は、個々のビットが 0 か 1 かを検証します。0 は偽、1 は真です。
bool getState(int bit)
{
return (state & (1 << bit)) != 0x0;
}
以下は、2 つの値にそれらのビットが含まれているかどうかをチェックする例です。各ビットが 2^BIT として表されると考えてください。
いくつかの演算子について簡単に説明します。最近、"&" 演算子について少し説明しました。今度は「|」オペレーター。
以下を実行する場合
int value = 31;
value |= 16;
value |= 16;
value |= 16;
value |= 16;
値は 31 のままです。これは、ビット 4 または 2^4=16 が既にオンになっているか、1 に設定されているためです。そのビットをオンにしてその値を返します。すでにオンになっている場合、変更は行われません。「|=」を使用して、実際に変数をその戻り値に設定します。
-> "value = value | 16;" の代わりに。「value |= 16;」を実行するだけです。
ここで、" & " と " | "をどのように利用できるかをもう少し詳しく見てみましょう。
/*
* This contains bits 0,1,2,3,4,8,9 turned on.
*/
const int CHECK = 1 | 2 | 4 | 8 | 16 | 256 | 512;
/*
* This is some value were we add bits 0 through 9, but we skip 0 and 8.
*/
int value = 2 | 4 | 8 | 16 | 32 | 64 | 128 | 512;
したがって、以下のコードを実行すると。
int return_code = value & CHECK;
戻りコードは 2 + 4 + 8 + 16 + 512 = 542 になります。
そのため、799 を確認していましたが、542 を受け取りました。これは、ビット o と 8 がオフラインであるためで、256 + 1 = 257 と 799 - 257 = 542 に等しくなります。
上記は、ビデオゲームを作成していて、ボタンが押されたかどうかを確認したいとしましょう。これらの各ビットを 1 回のチェックで簡単にチェックでき、すべての状態でブール チェックを実行するよりも何倍も効率的です。
ここで、常に反転するブール値があるとしましょう。
通常、次のようなことをします
bool state = false;
state = !state;
これは、" ^ " 演算子を使用してビットでも実行できます。
そのビットの全体の値を選択するために「1 << N」を実行したのと同じように。逆も同じことができます。"|=" が戻り値を格納する方法を示したのと同じように、"^=" でも同じことを行います。したがって、これが行うことは、そのビットがオンの場合、オフにすることです。オフの場合はオンにします。
void reverseState(int bit)
{
state ^= (1 << bit);
}
現在の状態に戻すこともできます。前の状態に戻したい場合は、"!=" を "==" に置き換えます。したがって、これが行うことは、反転を実行してから現在の状態をチェックすることです。
bool reverseAndGet(int bit)
{
return ((state ^= (1 << bit)) & (1 << bit)) != 0x0;
}
複数の単一ビット以外の bool 値を int に格納することもできます。通常、以下のように座標位置を書き出すとしましょう。
int posX = 0;
int posY = 0;
int posZ = 0;
ここで、これらが 1023 を超えなかったとしましょう。したがって、0 から 1023 までがこれらすべての最大距離でした。前述のように、他の目的で 1023 を選択します。0 と 2^N - 1 の間の値を強制する方法として「&」変数を操作できます。範囲が 0 ～ 1023 だったとします。「値と 1023」を実行すると、インデックス パラメータ チェックなしで常に 0 ～ 1023 の値になります。前述のように、これは 2 の累乗から 1 を引いた数でのみ機能することに注意してください。2^10 = 1024 - 1 = 1023。
たとえば、(値 >= 0 && 値 <= 1023) の場合はこれ以上ありません。
したがって、2^10 = 1024 で、0 から 1023 までの数値を保持するには 10 ビットが必要です。
したがって、10x3 = 30 であり、これはまだ 32 以下です。これらすべての値を int に保持するには十分です。
したがって、次のことを実行できます。それで、使用したビット数を確認します。0 + 10 + 20 を行います。ここに 0 を付けたのは、2^0 = 1 なので # * 1 = # であることを視覚的に示すためです。y << 10 が必要な理由は、x が 0 ～ 1023 の 10 ビットを使用するためです。したがって、それぞれに一意の値を持たせるには、y を 1024 倍する必要があります。次に、Z に 2^20 を掛ける必要があり、これは 1,048,576 です。
int position = (x << 0) | (y << 10) | (z << 20);
これにより、比較が高速になります。
今できること
return this.position == position;
に並置
return this.x == x && this.y == y && this.z == z;
では、それぞれの実際の位置が必要な場合はどうでしょうか?
x については、単純に次のようにします。
int getX()
{
return position & 1023;
}
次に、y については、左ビット シフトを実行してから AND を実行する必要があります。
int getY()
{
return (position >> 10) & 1023;
}
ご想像のとおり、Z は Y と同じですが、10 の代わりに 20 を使用します。
int getZ()
{
return (position >> 20) & 1023;
}
これを見た人は誰でも情報として価値があると思うでしょう:)。
本当に 1 ビットを使用したい場合は、char を使用して 8 つのブール値を格納し、bitshift を使用して必要な値を取得できます。それがより高速になるとは思えませんし、おそらくそのように作業することで多くの頭痛の種になるでしょうが、技術的には可能です。
余談ですが、このような試みは、変数に使用できるメモリが多くなくても、必要以上の処理能力があるシステムに役立つ可能性があります。しかし、あなたがそれを必要とすることはないと思います。