language-agnostic - ビット演算子の実際のユースケース

Question

次のビット演算子の実際のユースケースは何ですか？

と
XOR
いいえ
また
左/右シフト

score 249 · Accepted Answer

ビットフィールド (フラグ)
これらは、いくつかの「はいまたはいいえ」のプロパティによって状態が定義されるものを表す最も効率的な方法です。ACL が良い例です。たとえば、4 つの個別のアクセス許可 (読み取り、書き込み、実行、ポリシーの変更) がある場合、4 を無駄にするよりも、これを 1 バイトに格納することをお勧めします。これらは、利便性を高めるために多くの言語の列挙型にマップできます。
ポート/ソケットを介した通信に
は常に、チェックサム、パリティ、ストップビット、フロー制御アルゴリズムなどが含まれます。これらは通常、数値ではなく個々のバイトの論理値に依存します。時間。
圧縮、暗号化
これらは両方とも、ビット単位のアルゴリズムに大きく依存しています。例としてdeflateアルゴリズムを見てください。すべてがバイト単位ではなくビット単位です。
有限状態機械
私が主に話しているのは、ハードウェアの一部に組み込まれている種類のものですが、それらはソフトウェアにも見られます。これらは本質的に組み合わせです - それらは文字通り「コンパイル」されて一連の論理ゲートになる可能性があるためAND、OR、NOT、などとして表現する必要があります。
グラフィックス ここでは、グラフィックスプログラミングでこれらの演算子が使用されるすべての領域に入るには十分なスペースがありません。 XOR(or ^) は、同じ入力を 2 回適用すると最初の入力が取り消されるため、ここでは特に興味深いものです。古い GUI は、コストのかかる再描画の必要性を排除するために、選択の強調表示やその他のオーバーレイをこれに依存していました。これらは、低速のグラフィックスプロトコル (つまり、リモートデスクトップ) でも役立ちます。

これらは、私が思いついた最初のいくつかの例にすぎません。これは完全なリストではありません。

score 56 · Accepted Answer

56

奇妙ですか？

(value & 0x1) > 0

2で割り切れますか（偶数）？

(value & 0x1) == 0

于 2010-01-19T21:37:47.680 に答える

score 32 · Accepted Answer

CMS のセキュリティモデルを実装する際に、ビット演算を使用しました。ユーザーが適切なグループに属している場合にアクセスできるページがありました。ユーザーは複数のグループに属する可能性があるため、ユーザーグループとページグループの間に交差があるかどうかを確認する必要がありました。そのため、各グループに固有の 2 の累乗の識別子を割り当てました。たとえば、次のようになります。

Group A = 1 --> 00000001
Group B = 2 --> 00000010
Group C = 3 --> 00000100

これらの値を一緒に OR し、その値を (単一の int として) ページに格納します。たとえば、グループ A と B がページにアクセスできる場合、値 3 (バイナリでは 00000011) をページアクセスコントロールとして保存します。ほぼ同じ方法で、ORed グループ識別子の値をユーザーと一緒に保存して、ユーザーが属するグループを表します。

したがって、特定のユーザーが特定のページにアクセスできるかどうかを確認するには、値を AND で結び、値がゼロでないかどうかを確認するだけです。このチェックは単一の命令で実装され、ループやデータベースのラウンドトリップがないため、非常に高速です。

score 27 · Accepted Answer

低レベルのプログラミングが良い例です。たとえば、特定のビットをメモリマップドレジスタに書き込んで、ハードウェアの一部に目的の動作をさせる必要がある場合があります。

volatile uint32_t *register = (volatile uint32_t *)0x87000000;
uint32_t          value;
uint32_t          set_bit   = 0x00010000;
uint32_t          clear_bit = 0x00001000;

value = *register;            // get current value from the register
value = value & ~clear_bit;   // clear a bit
value = value | set_bit;      // set a bit
*register = value;            // write it back to the register

また、htonl()andはand演算子htons()を使用して実装されます (エンディアン(バイト順) がネットワーク順と一致しないマシン上):&|

#define htons(a) ((((a) & 0xff00) >> 8) | \
                  (((a) & 0x00ff) << 8))

#define htonl(a) ((((a) & 0xff000000) >> 24) | \
                  (((a) & 0x00ff0000) >>  8) | \
                  (((a) & 0x0000ff00) <<  8) | \
                  (((a) & 0x000000ff) << 24))

score 22 · Accepted Answer

たとえば、それらを使用して、パックされたカラー値から RGB(A) 値を取得します。

score 16 · Accepted Answer

ブーリアンフラグがたくさんある場合は、それらをすべて int に格納するのが好きです。

ビットごとのANDを使用してそれらを取得します。例えば：

int flags;
if (flags & 0x10) {
  // Turn this feature on.
}

if (flags & 0x08) {
  // Turn a second feature on.
}

等

score 15 · Accepted Answer

& = AND:
特定のビットをマスクします。
表示または非表示にする特定のビットを定義しています。0x0 & x はバイト内のすべてのビットをクリアしますが、0xFF は x を変更しません。0x0F は下位ニブルのビットを表示します。

変換:
int の -1 は 0xFFFFFFFF であり、long の -1 は 0xFFFFFFFFFFFFFFFF であるため、短い変数を長い変数にキャストするには、ビットを調整する必要があります。ID を保持するには、変換後にマスクを適用します。

|=OR
ビットを設定します。ビットがすでに設定されている場合は、個別に設定されます。多くのデータ構造 (ビットフィールド) には、独立して設定できる IS_HSET = 0、IS_VSET = 1 などのフラグがあります。フラグを設定するには、IS_HSET | を適用します。IS_VSET (C およびアセンブリでは、これは非常に読みやすいです)

^=XOR
同じまたは異なるビットを検索します。

~= NOT
ビットを反転します。

すべての可能なローカルビット操作は、これらの操作によって実装できることを示すことができます。したがって、必要に応じて、ビット操作のみで ADD 命令を実装できます。

いくつかの素晴らしいハック:

http://www.ugcs.caltech.edu/~wnoise/base2.html
http://www.jjj.de/bitwizardry/bitwizardrypage.html

score 11 · Accepted Answer

11

暗号化はすべてビット演算です。

于 2010-01-19T20:51:27.190 に答える

score 10 · Accepted Answer

データをハッシュするための迅速で汚れた方法としてそれらを使用できます。

int a = 1230123;
int b = 1234555;
int c = 5865683;
int hash = a ^ b ^ c;

score 9 · Accepted Answer

ちょうど 3 分前に bitwise-XOR ( ^) を使用して、PLC とのシリアル通信のチェックサムを計算しました...

score 8 · Accepted Answer

これは、バイト形式でビットマップイメージから色を読み取る例です。

byte imagePixel = 0xCCDDEE; /* Image in RRGGBB format R=Red, G=Green, B=Blue */

//To only have red
byte redColour = imagePixel & 0xFF0000; /*Bitmasking with AND operator */

//Now, we only want red colour
redColour = (redColour >> 24) & 0xFF;  /* This now returns a red colour between 0x00 and 0xFF.

この小さな例が役立つことを願っています....

score 7 · Accepted Answer

今日の現代言語の抽象化された世界では、それほど多くはありません。ファイル IO は頭に浮かぶ簡単なものですが、それは既に実装されているものに対してビット単位の操作を実行し、ビット単位の操作を使用するものを実装していません。それでも、簡単な例として、このコードはファイルの読み取り専用属性を削除する方法を示しています (FileMode.Create を指定する新しい FileStream で使用できるようにするため)。

//Hidden files posses some extra attibutes that make the FileStream throw an exception
//even with FileMode.Create (if exists -> overwrite) so delete it and don't worry about it!
if(File.Exists(targetName))
{
    FileAttributes attributes = File.GetAttributes(targetName);

    if ((attributes & FileAttributes.ReadOnly) == FileAttributes.ReadOnly)
        File.SetAttributes(targetName, attributes & (~FileAttributes.ReadOnly));

    File.Delete(targetName);
}

カスタム実装に関しては、最近の例を次に示します。分散アプリケーションの 1 つのインストールから別のインストールに安全なメッセージを送信するための「メッセージセンター」を作成しました。基本的には電子メールに似ており、Inbox、Outbox、Sent などを完備していますが、開封確認を含む配信が保証されているため、"inbox" と "sent" 以外にも追加のサブフォルダーがあります。これが何を意味するかというと、何が「受信トレイ」または「送信済みフォルダー」にあるのかを一般的に定義する必要がありました。送信済みフォルダのうち、何が既読で何が未読かを知る必要があります。未読のうち、何が受信され、何が受信されていないかを知る必要があります。この情報を使用して、ローカルデータソースをフィルター処理し、適切な情報を表示する動的 where 句を作成します。

列挙型をまとめる方法は次のとおりです。

    public enum MemoView :int
    {
        InboundMemos = 1,                   //     0000 0001
        InboundMemosForMyOrders = 3,        //     0000 0011
        SentMemosAll = 16,                  //     0001 0000
        SentMemosNotReceived = 48,          //     0011
        SentMemosReceivedNotRead = 80,      //     0101
        SentMemosRead = 144,                //     1001
        Outbox = 272,                       //0001 0001 0000
        OutBoxErrors = 784                  //0011 0001 0000
    }

これが何をするかわかりますか？「Inbox」列挙値 InboundMemos と AND (&) することで、InboundMemosForMyOrders が受信トレイにあることがわかります。

以下は、現在選択されているフォルダーのビューを定義するフィルターを構築して返すメソッドの要約バージョンです。

    private string GetFilterForView(MemoView view, DefaultableBoolean readOnly)
    {
        string filter = string.Empty;
        if((view & MemoView.InboundMemos) == MemoView.InboundMemos)
        {
            filter = "<inbox filter conditions>";

            if((view & MemoView.InboundMemosForMyOrders) == MemoView.InboundMemosForMyOrders)
            {
                filter += "<my memo filter conditions>";
            }
        }
        else if((view & MemoView.SentMemosAll) == MemoView.SentMemosAll)
        {
            //all sent items have originating system = to local
            filter = "<memos leaving current system>";

            if((view & MemoView.Outbox) == MemoView.Outbox)
            {
                ...
            }
            else
            {
                //sent sub folders
                filter += "<all sent items>";

                if((view & MemoView.SentMemosNotReceived) == MemoView.SentMemosNotReceived)
                {
                    if((view & MemoView.SentMemosReceivedNotRead) == MemoView.SentMemosReceivedNotRead)
                    {
                        filter += "<not received and not read conditions>";
                    }
                    else
                        filter += "<received and not read conditions>";
                }
            }
        }

        return filter;
    }

非常に単純ですが、通常はビット単位の操作を必要としない抽象化レベルでのきちんとした実装です。

score 7 · Accepted Answer

ビットごとの & は、バイトの特定の部分をマスク/抽出するために使用されます。

1バイト変数

 01110010
&00001111 Bitmask of 0x0F to find out the lower nibble
 --------
 00000010

特にシフト演算子 (<< >>) は、計算によく使用されます。

score 5 · Accepted Answer

通常、ビット演算は乗算/除算よりも高速です。したがって、変数 x にたとえば 9 を掛ける必要がある場合は、x<<3 + xよりも数サイクル速くなりx*9ます。このコードが ISR 内にある場合、応答時間を節約できます。

同様に、配列を循環キューとして使用する場合は、ビット単位の操作でラップアラウンドチェックを処理する方が高速 (かつエレガント) です。(配列サイズは 2 のべき乗である必要があります)。例:を挿入/削除する場合は、tail = ((tail & MASK) + 1)の代わりにを使用できます。tail = ((tail +1) < size) ? tail+1 : 0

また、エラーフラグに複数のエラーコードをまとめて保持する場合は、各ビットに個別の値を保持できます。チェックとして、個々のエラーコードとの AND を使用できます。これは、Unix エラーコードで使用されます。

また、n ビットのビットマップは、非常にクールでコンパクトなデータ構造になります。サイズ n のリソースプールを割り当てたい場合は、n ビットを使用して現在のステータスを表すことができます。

score 4 · Accepted Answer

Base64 エンコーディングは一例です。Base64 エンコーディングは、電子メールシステム (およびその他の目的) を介して送信するための印刷可能な文字としてバイナリデータを表すために使用されます。Base64 エンコーディングは、一連の 8 ビットバイトを 6 ビット文字ルックアップインデックスに変換します。ビット操作、シフト、論理和、否定は、Base64 のエンコードとデコードに必要なビット操作を実装するのに非常に役立ちます。

もちろん、これは数え切れないほどの例の 1 つにすぎません。

score 4 · Accepted Answer

不動点計算については誰も言及していないようです。

（ええ、私は年をとっていますよね？）

score 4 · Accepted Answer

ビット単位の演算子は、長さが 2 の累乗である配列をループする場合に便利です。多くの人が言及したように、ビット単位の演算子は非常に便利で、Flags、Graphics、 Networking、Encryptionで使用されます。それだけでなく、非常に高速です。私の個人的なお気に入りの使用法は、条件なしで配列をループすることです。ゼロインデックスベースの配列 (たとえば、最初の要素のインデックスが 0) があり、それを無期限にループする必要があるとします。無期限とは、最初の要素から最後に行き、最初に戻ることを意味します。これを実装する 1 つの方法は次のとおりです。

int[] arr = new int[8];
int i = 0;
while (true) {
    print(arr[i]);
    i = i + 1;
    if (i >= arr.length) 
        i = 0;
}

これは最も単純なアプローチです。ifステートメントを避けたい場合は、次のようにモジュラスアプローチを使用できます。

int[] arr = new int[8];
int i = 0;
while (true) {
    print(arr[i]);
    i = i + 1;
    i = i % arr.length;
}

これら 2 つの方法の欠点は、モジュラス演算子が整数除算後の剰余を探すためコストがかかることです。最初のメソッドは、反復ごとにifステートメントを実行します。ただし、ビット単位の演算子を使用すると、配列の長さが 2 のべき乗である場合、 (ビット単位の and) 演算子0 .. length - 1を使用して、 so のようなシーケンスを簡単に生成できます。したがって、これを知っていると、上記のコードは次のようになります&i & length

int[] arr = new int[8];
int i = 0;
while (true){
    print(arr[i]);
    i = i + 1;
    i = i & (arr.length - 1);
}

これがどのように機能するかです。バイナリ形式では、2 の累乗から 1 を引いた数はすべて 1 だけで表されます。たとえば、バイナリの 3 は11、7 は111、15 は1111などです。&では、2 進数の 1 だけで構成される数に対して任意の数を指定するとどうなるでしょうか? これを行うとしましょう：

num & 7;

numが 7 以下の場合、1 で処理さnumれた各ビット&はそれ自体であるため、結果はになります。numが 7 よりも大きい場合、&操作中にコンピュータは 7 の先頭のゼロを考慮しますが、これはもちろん操作後もゼロ&のままであり、末尾の部分のみが残ります。9 & 7バイナリの場合のように、次のようになります

1001 & 0111

結果は 0001 になります。これは 10 進数で 1 であり、配列の 2 番目の要素をアドレス指定します。

score 3 · Accepted Answer

数xは2の累乗ですか？（たとえば、カウンターがインクリメントされ、アクションが対数回数だけ実行されるアルゴリズムで役立ちます）

(x & (x - 1)) == 0

整数の最上位ビットはどれxですか？（これは、たとえば、より大きい2の最小電力を見つけるために使用できますx）

x |= (x >>  1);
x |= (x >>  2);
x |= (x >>  4);
x |= (x >>  8);
x |= (x >> 16);
return x - (x >>> 1); // ">>>" is unsigned right shift

1整数の最下位ビットはどれxですか？（2で割り切れる回数を見つけるのに役立ちます。）

x & -x

score 3 · Accepted Answer

数値 mod(%) を特定の 2 の累乗で計算したいyourNumber & 2^N-1場合は、を使用できます。この場合はと同じyourNumber % 2^Nです。

number % 16 = number & 15;
number % 128 = number & 127;

これはおそらく、2 ^ N という非常に大きな被除数を持つモジュラス操作の代替としてのみ有用です...しかし、それでもモジュラス操作に対する速度の向上は、.NET 2.0 での私のテストでは無視できます。最近のコンパイラはすでにこのような最適化を行っていると思います。これについて詳しく知っている人はいますか？

score 2 · Accepted Answer

複数選択オプションに使用します。このようにして、10以上ではなく1つの値のみを保存します

score 2 · Accepted Answer

また、SQL リレーショナルモデルでも便利です。次のテーブルがあるとします。BlogEntry、BlogCategory

伝統的に、BlogEntryCategory テーブルを使用してそれらの間に nn 関係を作成できます。または、BlogCategory レコードがそれほど多くない場合は、フラグ付きの列挙型で行うのと同じように、BlogEntry の 1 つの値を使用して複数の BlogCategory レコードにリンクできます。ほとんどの RDBMS には、その「フラグ付き」列を選択するための非常に高速な演算子...

score 1 · Accepted Answer

ハノイの塔の線形ソリューションは、ビット単位の演算を使用して問題を解決します。

public static void linear(char start, char temp, char end, int discs)
{
    int from,to;
    for (int i = 1; i < (1 << discs); i++) {
        from = (i & i-1) % 3;
        to = ((i | i-1) + 1) % 3;
        System.out.println(from+" => "+to);
    }
}

このソリューションの説明はここにあります

score 1 · Accepted Answer

私が最初にCプログラミングを始めたときはいつでも、真理値表とそのすべてを理解していましたが、この記事http://www.gamedev.net/reference/articles/article1563.aspを読むまで、実際にそれを使用する方法についてはすべてクリックしませんでした。（実際の例を示します）

score 1 · Accepted Answer

オプションの組み合わせを 1 つの整数に格納するためにビット演算をよく使用します。

int options = 0;

ここで、1、2、4、8、16 、...とOPTION1定義できます。OPTION2OPTION3OPTION4OPTION5

void addOption(int option)演算子を使用して|、オプションにオプションを追加します。

boolean hasOption(int option)&演算子を使用して、オプション内のオプションをテストします。

score 1 · Accepted Answer

ここで私の質問には実際の使用があります-
最初の WM_KEYDOWN 通知のみに応答しますか?

Windows C API ビット 30 で WM_KEYDOWN メッセージを使用する場合、以前のキーの状態を指定します。メッセージが送信される前にキーが押されている場合、値は 1 であり、キーが押されている場合、値は 0 です。

score 1 · Accepted Answer

乗算と除算のより効率的な方法として、いくつかのゲーム開発本で見たことがあります。

2 << 3 == 2 * 8 
32 >> 4 == 32 / 16

score 1 · Accepted Answer

それらは主にビット単位の操作に使用されます（驚き）。PHP コードベースにある実際の例をいくつか紹介します。

文字コード：

if (s <= 0 && (c & ~MBFL_WCSPLANE_MASK) == MBFL_WCSPLANE_KOI8R) {

データ構造:

ar_flags = other->ar_flags & ~SPL_ARRAY_INT_MASK;

データベースドライバー:

dbh->transaction_flags &= ~(PDO_TRANS_ACCESS_MODE^PDO_TRANS_READONLY);

コンパイラの実装:

opline->extended_value = (opline->extended_value & ~ZEND_FETCH_CLASS_MASK) | ZEND_FETCH_CLASS_INTERFACE;

score 0 · Accepted Answer

非常に具体的な例ですが、数独ソルバーをより高速に実行するためにそれらを使用しました（友人と競争していました）

各列、行、および3x3は符号なし整数として表され、数値を設定すると、関連する列、行、および3x3の正方形に設定された数値の適切なビットにフラグが立てられます。

これにより、特定の正方形に配置できる可能性のある数値を簡単に確認できます。これは、右の列、行、および3x3の正方形をORで結合し、特定の法的な値を表すマスクを残すためではないためです。ポジション。

それが理にかなっていることを願っています。

score 0 · Accepted Answer

私はそれらをオプションハンドラーとして使用します。たとえば、特定のリソースを説明するためのアクセス制御リストで使用します。

この記事をご覧くださいhttp://planetozh.com/blog/2006/05/php-bitwise-operators-example-of-use/

編集：

もう1つのリンク： http： //blog.code-head.com/how-to-write-a-permission-system-using-bits-and-bitwise-operations-in-php

score 0 · Accepted Answer

データベースの世界におけるもう1つの実際のアプリケーションは、SETと呼ばれるデータ型を持つMySQLです。

ビット単位の演算子は、DBMSがSETデータ型を格納するためのものです。セットはスペースを節約できます。

Element    SET Value    Decimal Value
Travel      00000001    1
Sports      00000010    2
Dancing    00000100    4
Fine Dining   00001000  8

score 0 · Accepted Answer

少し前に、バイナリライター/リーダーを示す小さな wiki 記事を書きました。これはビットレベルで動作し、ビット単位の演算子を使用してデータをパックする方法を示します。ゲームでのアプリケーションがあるため、これはおそらく「現実世界」の例です。

score 0 · Accepted Answer

一般的な用途はアラインメントです。たとえば、データを 4 バイトまたは 16 バイトの境界にアラインする必要があります。これは、アラインされていないロード/ストアが高価な RISC プロセッサでは非常に一般的です (修正が必要な例外ハンドラーをトリガーするため)。整列されていない負荷まで）またはまったく許可されていません。

2 の累乗である配置の場合、次に配置された位置は次のように計算できます。

aligned_offset = alignment + ((current_offset - 1) & ~(alignment - 1))

したがって、4 バイトのアラインメントと現在のオフセットが 9 の場合は、次のようになります。

aligned_offset = 4 + ((9-1) & ~(4-1)) = 4 + (8 & 0xFFFFFFFC) = 4+ 8  = 12

したがって、次の 4 バイトにアラインされたオフセットは 12 になります

score 0 · Accepted Answer

まだ誰も言及されていないコレクションです。場合によっては、10 個または 20 個の可能な値のみなど、可能な値の小さなコレクションがあり、それらのいくつかをセットに保持したい場合があります。Set確かに、バッキングハッシュテーブルを使用する可能性が最も高い通常の実装を使用できます。しかし、可能な値のセットが非常に小さいため、これは時間とスペースの無駄です。代わりに、セットを単一のintまたは値に格納できます。これは、私の記憶が正しければlongJavaが行うこととまったく同じです。EnumSet

score 0 · Accepted Answer

私は常に、ビット単位の操作は非常に単純な操作であると想定していました。そのため、実行時間が重要な場合、ビットセットを介して実装されたソリューションは、アルゴリズムに応じて実行時間を一定量改善できます。

language-agnostic - ビット演算子の実際のユースケース

41 に答える 41

Related

Reference