14

代数法則の観点から考えると、代数と同様に、ビット操作の領域に存在する公式のガイドラインがあるかどうか疑問に思っていました。

代数の例

a - b =/= b - a

させa = 7てb = 5

  • a - b = 2
  • b - a = -2

させa = 10てb = 3

  • a - b = 7
  • b - a = -7

したがってif a > b、b - aは に相当する負の値になりa - bます。このため、と言えます

|a - b| = |b - a|。

どこ|x|で の絶対値を示しますx。

ビット単位の例

a | b =/= a + b

      00001010 = 10
  OR  00000101 = 5 
  -----------------
      00001111 = 15

符号なしバイト操作に注意してください:10 | 5 = 15と同義です。10 + 5 = 15

ただし、両方aとbが 5 に等しい場合OR、結果は 5 になりa = bます。これは、まったく同じビットを互いに比較しているだけであるため、新しい結果は何もないことを意味します。

同様に、 の場合b = 7、それらa = 10をOR15 にします。これは、

    00001010 = 10
 OR 00000111 = 7
 -----------------
    00001111 = 15

したがって、効果的にそれを結論付けることができa | b =/= a + bます。

4

1 に答える 1

38

オペランドの対応するビット間に適用される単なるブール演算子であるビット演算は、ブール代数の法則に類似した法則に従います。次に例を示します。

  • AND (&): 可換、連想、恒等 (0xFF)、消滅 (0x00)、冪等
  • OR (|): 可換、連想、恒等 (0x00)、消滅 (0xFF)、冪等
  • XOR (^): 可換、連想、恒等 (0x00)、逆 (自身)
  • NOT (~)：逆（自身）

AND と OR は互いに吸収し合います。

  • a & (a | b) = a
  • a | (a & b) = a

次のような分配演算子のペアがいくつかあります。

  • AND オーバー OR:a & (b | c) = (a & b) | (a & c)
  • XOR 上の AND:a & (b ^ c) = (a & b) ^ (a & c)
  • OR の上 AND:a | (b & c) = (a | b) & (a | c)

ただし、XOR は AND または OR を介して分配されず、OR も XOR を介して分配されないことに注意してください。

DeMorgans 法は、さまざまな形で適用されます。

  • ~(a & b) = ~a | ~b
  • ~(a | b) = ~a & ~b

XOR と AND に関連するいくつかの法則は、体 ℤ/2ℤ について推論することによって見つけることができます。ここで、加算は XOR に対応し、乗算は AND に対応します。

  • AND は XOR で分配します
  • 和の積を計算する:(a ^ b) & (c ^ d) = (a & c) ^ (a & d) ^ (b & c) ^ (b & d)

算術演算とビット演算を組み合わせた法則がいくつかあります。

  • 次を追加して減算します。a - b = ~(~a + b)
  • キャリーを個別に追加します。a + b = (a ^ b) + ((a & b) << 1)
  • に変換minしmax、その逆: min(a, b) = ~max(~a, ~b)、max(a, b) = ~min(~a, ~b)

エッジにプッシュされたビットの「破壊」のため、シフトには反転がありません

left shift (<<): 連想、分配、同一性 (0x00)

right shift (>>): 連想、分配、同一性 (0x00)

rotate left (rl): 連想、分配、同一性 (0x00)、反転 ( rr)

rotate right (rr): 連想、分配、同一性 (0x00)、反転 ( rl)

シフトには逆がありませんが、シフトを含む一部の式には、他の法則の結果として逆があります。たとえば、次のようになります。

  • x + (x << k)これは事実上、奇数による乗算であり、奇数には 2 の累乗を法とする剰余乗法逆数があるためです。の場合x + (x << 1) = x * 3、逆になりますx * 0xAAAAAAAB(32 ビットの場合、他のサイズの定数を調整します)。
  • x ^ (x << k)同様の理由で逆数がありますが、キャリーレス乗算との対応によるものです。
  • 同様にx ^ (x >> k)（符号なしの右シフトを使用）には逆があり、上記の「ミラーイメージ」にすぎません。
于 2017-08-27T20:56:14.423 に答える