C/C++ ビット配列またはビットベクトル

https://stackoverflow.com/questions/4604130

25-09-2019
|

質問

私は C/C++ プログラミングを学習していて、「ビット配列」または「ビットベクトル」の使用法に遭遇しました。彼らの目的が理解できないのでしょうか？ここに私の疑問があります -

それらはブール値フラグとして使用されますか?
使えますか int 代わりに配列?(もちろんメモリは増えますが...)
ビットマスキングの概念とは何ですか?
ビットマスキングが適切なフラグを取得するための単純なビット操作である場合、どのようにプログラムすればよいでしょうか?この操作を頭の中で実行して、10 進数と比較してフラグが何になるかを確認するのは難しくありませんか?

より深く理解できるよう、アプリケーションを探しています。たとえば -

Q. 範囲 (1 ～ 100 万) の整数を含むファイルが与えられます。一部重複しているため、一部の番号が欠落しています。欠落している数字を見つける最速の方法を見つけますか？

上記の質問に対して、ビット配列を使用するように指示する解決策を読みました。各整数をビットに格納するにはどうすればよいでしょうか?

解決

あなたは配列と数値、特に 2 進数を操作することが何を意味するのかを混乱していると思います。

これについて例を挙げて説明します。多数のエラーメッセージがあり、それらを関数からの戻り値で返したいとします。ここで、エラーに 1、2、3、4... というラベルを付けるとよいでしょう。これは頭では理解できますが、では、数字が 1 つだけ与えられた場合、どのエラーが発生したかをどのように判断するのでしょうか?

ここで、エラーに 1、2、4、8、16... というラベルを付けてみます。基本的には 2 のべき乗を増加させます。なぜこれが機能するのでしょうか?さて、基数 2 を操作するときは、次のような数値を操作することになります。 00000000 ここで、各桁は 2 のべき乗に右からの位置を乗じた値に対応します。したがって、エラー 1、4、および 8 が発生したとします。さて、それは次のように表すことができます 00001101. 。逆に、1 桁目は 1*2^0、3 桁目は 1*2^2、4 桁目は 1*2^3 となります。全部足すと13になります。

ビットマスクを適用することで、そのようなエラーが発生したかどうかをテストできるようになりました。たとえば、エラーが発生したかどうかを調べたい場合は、 8 が発生した場合は、8 = のビット表現を使用します。 00001000. 。ここで、そのエラーが発生したかどうかを抽出するには、バイナリなどを使用します。

  00001101
& 00001000
= 00001000

and がどのように機能するか、または上記のことから推測できると思います。桁ごとに動作し、2 つの数字が両方とも 1 の場合、結果は 1 になり、そうでない場合は 0 になります。

ここで、C では次のようになります。

int func(...)
{
    int retval = 0;

    if ( sometestthatmeans an error )
    {
        retval += 1;
    }


    if ( sometestthatmeans an error )
    {
        retval += 2;
    }
    return retval
}

int anotherfunc(...)
{
    uint8_t x = func(...)

    /* binary and with 8 and shift 3 plaes to the right
     * so that the resultant expression is either 1 or 0 */
    if ( ( ( x & 0x08 ) >> 3 ) == 1 )
    {
        /* that error occurred */
    }
}

さて、実践編です。メモリがまばらで、プロトコルに冗長な XML などの余裕がなかったときは、フィールドを非常に多くのビット幅で区切るのが一般的でした。そのフィールドでは、さまざまなビット (フラグ、2 の累乗) を特定の意味に割り当て、二項演算を適用してそれらが設定されているかどうかを推測し、それらを操作します。

また、二項演算は、コンピューターの基礎となる電子機器と考え方が近いことも付け加えておきます。ビットフィールドがさまざまな回路の出力 (電流が流れるかどうか) に対応するかどうかを想像してください。上記の回路を十分に組み合わせて使用すると、...コンピュータ。

他のヒント

ビット配列の使用法については、次のとおりです。

数値が 100 万「だけ」あることがわかっている場合は、100 万ビットの配列を使用します。最初はすべてのビットが 0 で、数値を読み取るたびに、この数値をインデックスとして使用し、このインデックス内のビットを 1 に変更します (まだ 1 でない場合)。

すべての数値を読み取った後、欠落している数値は配列内のゼロのインデックスになります。

たとえば、0 ～ 4 の数値のみがある場合、配列は最初は次のようになります。0 0 0 0 0。数字を読むと：3、2、2アレイは次のようになります。3 を読み取ります --> 0 0 0 1 0。3 を読み取ります (再度) --> 0 0 0 1 0。2 を読み取ります --> 0 0 1 1 0。ゼロのインデックスを確認します。0、1、4 - これらは欠落している数字です

ところで、もちろんビットの代わりに整数を使用することもできますが、(システムによっては) 32 倍のメモリが必要になる可能性があります。

シヴァン

ビット配列またはビットベクトルは、 ブール値の配列. 。通常、ブール変数には少なくとも 1 バイトのストレージが必要ですが、ビット配列/ベクトルでは 1 ビットだけが必要です。このようなデータが大量にある場合、メモリを大幅に節約できるため、これは便利です。

別の使い方は次のとおりです。 標準変数に正確に適合しない数値 サイズは 8、16、32、または 64 ビットです。この方法で、サイズが 2 ビットと 10 ビットの 4 ビットで構成される数値を 16 ビットのビットベクトルに格納できます。通常は、サイズが 8、8、16 ビットの 3 つの変数を使用する必要があるため、ストレージの 50% しか無駄になりません。

ただし、これらすべての用途がビジネスアプリケーションで使用されることは非常にまれで、ドライバーとインターフェイスするときに頻繁に使用されます。 ピンボーク/相互運用性 機能と実行 低レベルのプログラミング.

ビットベクトルのビット配列は、位置から何らかのビット値へのマッピングとして使用されます。はい、基本的には Bool の配列と同じものですが、一般的な Bool 実装は 1 ～ 4 バイトの長さであり、使用するスペースが多すぎます。

ワードの配列とバイナリマスキング操作、およびそれらを格納および取得するためのシフトを使用することで、同じ量のデータをより効率的に格納できます (全体的なメモリ使用量が減り、メモリへのアクセスが減り、キャッシュミスが減り、メモリページスワップが減ります)。個々のビットにアクセスするコードは依然として非常に簡単です。

C 言語にはいくつかのビットフィールドサポートも組み込まれています (次のように記述します)。 int i:1; ただし、配列では利用できず、全体的な結果を制御する能力が低くなります (実装の詳細はコンパイラとアライメントの問題に依存します)。

以下は、「欠落している番号を検索する」という質問に対する答えとして考えられる方法です。物事をシンプルにするために int サイズを 32 ビットに固定しましたが、移植性を高めるために sizeof(int) を使用して記述することもできます。そして (コンパイラとターゲットプロセッサに応じて) コードを高速化するには、次の方法を使用する必要があります。 >> 5 の代わりに / 32 そして & 31 の代わりに % 32, しかし、それはアイデアを提供するだけです。

#include <stdio.h>
#include <errno.h>
#include <stdint.h>

int main(){
    /* put all numbers from 1 to 1000000 in a file, except 765 and 777777 */
    {
        printf("writing test file\n");
        int x = 0;
        FILE * f = fopen("testfile.txt", "w");
        for (x=0; x < 1000000; ++x){
            if (x == 765 || x == 777760 || x == 777791){
                continue;
            }
            fprintf(f, "%d\n", x);
        }
        fprintf(f, "%d\n", 57768); /* this one is a duplicate */
        fclose(f);
    }

    uint32_t bitarray[1000000 / 32];

    /* read file containing integers in the range [1,1000000] */
    /* any non number is considered as separator */
    /* the goal is to find missing numbers */
    printf("Reading test file\n");
    {
        unsigned int x = 0;
        FILE * f = fopen("testfile.txt", "r");
        while (1 == fscanf(f, " %u",&x)){
            bitarray[x / 32] |= 1 << (x % 32);
        }
        fclose(f);
    }
    /* find missing number in bitarray */
    {
        int x = 0;
        for (x=0; x < (1000000 / 32) ; ++x){
            int n = bitarray[x];
            if (n != (uint32_t)-1){
                printf("Missing number(s) between %d and %d [%x]\n",
                    x * 32, (x+1) * 32, bitarray[x]);
                int b;
                for (b = 0 ; b < 32 ; ++b){
                    if (0 == (n & (1 << b))){
                        printf("missing number is %d\n", x*32+b);
                    }
                }
            }
        }
    }
}

これは、ビットフラグの保存と、1 バイトが多数のビットフィールドに分割されるさまざまなバイナリプロトコルフィールドの解析に使用されます。これは、TCP/IP などのプロトコル、ASN.1 エンコーディング、OpenPGP パケットなどで広く使用されています。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow

C/C++ ビット配列またはビット ベクトル

C/C++ ビット配列またはビットベクトル