10

私はビット演算子が初めてです。

最終結果を得るために論理関数がどのように機能するかを理解しています。たとえば、AND2 つの数値をビットごとに処理すると、最終結果はANDそれらの 2 つの数値 ( 1 & 0 = 0; 1 & 1 = 1; 0 & 0 = 0) になります。OR、XOR、 と同じNOTです。

私が理解していないのは、それらのアプリケーションです。私はどこでも探してみましたが、ほとんどはビット単位の操作がどのように機能するかを説明しているだけです。すべてのビット演算子の中で、シフト演算子 (乗算と除算) の適用しか理解していません。マスキングにも出会いました。マスキングはビットごとに行われることは理解してANDいますが、その目的は何ですか?また、どこでどのように使用できますか?

マスキングの使い方について詳しく教えてください。と の同様の用途はORありXORますか?

4

6 に答える 6

19

ビットごとの演算子の低レベルの使用例は、基数 2 の計算を実行することです。数値が 2 のべき乗であるかどうかをテストするためのよく知られたトリックがあります。

if ((x & (x - 1)) == 0) {
    printf("%d is a power of 2\n", x);
}

ただし、より高いレベルの機能であるセット操作も提供できます。ビットの集まりをセットと考えることができます。説明するために、1 バイトの各ビットが 8 つの異なる項目を表すようにしましょう。たとえば、太陽系の惑星を考えてみましょう (冥王星はもはや惑星とは見なされないため、8 ビットで十分です!)。

#define Mercury (1 << 0)
#define Venus   (1 << 1)
#define Earth   (1 << 2)
#define Mars    (1 << 3)
#define Jupiter (1 << 4)
#define Saturn  (1 << 5)
#define Uranus  (1 << 6)
#define Neptune (1 << 7)

次に、次のように惑星のコレクション (サブセット) を形成できます|。

unsigned char Giants = (Jupiter|Saturn|Uranus|Neptune);
unsigned char Visited = (Venus|Earth|Mars);
unsigned char BeyondTheBelt = (Jupiter|Saturn|Uranus|Neptune);
unsigned char All = (Mercury|Venus|Earth|Mars|Jupiter|Saturn|Uranus|Neptune);

&これで、 a を使用して、2 つのセットに交差があるかどうかをテストできます。

if (Visited & Giants) {
    puts("we might be giants");
}

この^演算は、2 つのセット (セットの和集合から交差を差し引いたもの) の違いを確認するためによく使用されます。

if (Giants ^ BeyondTheBelt) {
    puts("there are non-giants out there");
}

したがって、|ユニオン、&交差点、^ユニオンから交差点を差し引いたものと考えてください。

セットを表現するビットのアイデアを受け入れると、それらのセットを操作するのに役立つビット単位の演算が自然に存在します。

于 2013-06-19T01:21:55.080 に答える
3

前述のように、小さなセット。驚くほど多くの操作をすばやく実行できます。交差と結合と (対称) 差は明らかに些細なことですが、たとえば、次のことも効率的に実行できます。

  1. セット内の最下位のアイテムを取得するx & -x
  2. でセットから最下位のアイテムを削除しますx & (x - 1)
  3. 現在の最小アイテムより小さいすべてのアイテムを追加
  4. 現在の最小アイテムより上のすべてのアイテムを追加
  5. それらのカーディナリティを計算します（アルゴリズムは自明ではありませんが）
  6. 何らかの方法でセットを並べ替えます。つまり、アイテムのインデックスを変更します (すべての並べ替えが同じように効率的であるとは限りません)。
  7. 同じ数の項目を含む次の集合を辞書式に計算する (Gosper's Hack)

1 と 2 およびそれらのバリエーションを使用して、小さなグラフで効率的なグラフ アルゴリズムを構築できます。たとえば、The Art of Computer Programming 4A のアルゴリズム R を参照してください。

ビット演算のその他のアプリケーションには、次のものが含まれますが、これらに限定されません。

  • 多くのボードゲームで重要なビットボード。ビットボードのないチェスは、サンタのいないクリスマスのようなものです。スペース効率の高い表現であるだけでなく、ビットボードを使用して自明でない計算を直接実行できます (双曲線のクインテッセンスを参照)。
  • 横方向のヒープ、および最も近い共通の祖先を見つけて範囲最小クエリを計算する際のそれらのアプリケーション。
  • 効率的なサイクル検出 (HAKMEM にある Gosper のループ検出)
  • それらを分解および再構築せずに Z 曲線アドレスにオフセットを追加する (テッセラル演算を参照)

これらの用途はより強力ですが、高度で、まれで、非常に特殊です。しかし、彼らは、ビット単位の操作が、古い低レベルの時代から残された単なるかわいいおもちゃではないことを示しています。

于 2013-06-19T11:03:55.423 に答える
3

ビットごとの AND のアプリケーションの 1 つは、1 つのビットがバイトに設定されているかどうかをチェックすることです。これは、オーバーヘッドを削減するために、プロトコル ヘッダーが可能な限り多くの情報を最小の領域に詰め込もうとするネットワーク通信で役立ちます。

たとえば、IPv4 ヘッダーは、6 番目のバイトの最初の 3 ビットを使用して、指定された IP パケットをフラグメント化できるかどうか、フラグメント化できる場合は、指定されたパケットのフラグメントがさらに続くことを期待するかどうかを判断します。これらのフィールドが代わりに int (1 バイト) のサイズである場合、各 IP パケットは必要以上に 21 ビット大きくなります。これは、毎日インターネットを介して膨大な量の不要なデータに変換されます。

これらの 3 ビットを取得するには、ビットごとの AND をビット マスクと共に使用して、それらが設定されているかどうかを判断します。

char mymask = 0x80;
if(mymask & (ipheader + 48) == mymask)
  //the second bit of the 6th byte of the ip header is set
于 2013-06-19T01:12:03.350 に答える
1

マイクロコントローラー アプリケーションでは、ビットごとに使用してポートを切り替えることができます。下の図で、1 つのポートをオンにして残りをオフにしたい場合は、次のコードを使用できます。

void main() 
{
     unsigned char ON = 1;
     TRISB=0;
     PORTB=0;
     while(1){
        PORTB = ON;
        delay_ms(200);
        ON = ON << 1;
        if(ON == 0) ON=1;
     }
}

ここに画像の説明を入力

于 2016-08-23T13:22:13.893 に答える
1

例 1

「一緒に機能する」ブール値が 10 個あれば、コードを大幅に簡素化できます。

int B1 = 0x01;
int B2 = 0x02;
int B10 = 0x0A;

int someValue = get_a_value_from_somewhere();

if (someValue & (B1 + B10)) {
    // B1 and B10 are set
}

例 2

ハードウェアとのインターフェース。ハードウェア上のアドレスは、インターフェイスを制御するためにビット レベルのアクセスが必要な場合があります。たとえば、バッファのオーバーフロー ビットや、8 つの異なる状態を示すステータス バイトなどです。ビット マスキングを使用すると、必要な実際の情報を取得できます。

if (register & 0x80) {
    // top bit in the byte is set which may have special meaning.
}

これは実際には、例 1 の特殊なケースにすぎません。

于 2013-06-19T01:05:59.003 に答える