ビット演算メモ

ハッカーのたのしみ読んでます。実はこの本、「解説が殆ど無い」。提示されているのは式のみ。後は自分で探るしかないのだ・・・メモメモ。


記号はCの演算子。=は等号。

&

マスク。共通するビット以外をオフにする効果を持つ。


例:IPアドレス & サブネットマスク = ネットワークアドレス

192.168.1.100 & 255.255.0.0 = 192.168.0.0

|

ビットを立てる。とにかくビットが立ってたらビットを立てる。


例:ファイルhoge.scmの権限は644なので、実行権限(111)を与える。chmod +x hoge.scm

644 | 111 = 755 (8進数)

~(not)

ビットの反転。1の補数を取る。

^(xor)

繰上り無しの足し算。mod2世界の足し算と覚えておくと忘れない。

1 ^ 1 = 0
1 + 1 = 0 (mod 2)

-1

最右のビットを消して、右側にビットを立てる。

最右ビットを消すマスクの作成に。

10101000 - 1 = 101000111

+1

最右の1の連続をまとめて、左側にビットを立てる。

イマイチ謎が多い奴。

11001111 + 1 = 11010000

単項-

2の補数を取る。反転させて+1と覚えておくと便利。

最右ビットのみを残すマスクの作成。

-00101000 = 11010111 + 1 = 11011000

<<

左シフト。

2倍する。
x << 1 = 2 * x

>>

右シフト。マイナスの取り扱いに注意。

  • x >> 31 (符号付32ビット)
    • プラスか0なら0
    • マイナスで符号付シフトなら~0
    • マイナスで符号無しシフトなら1

超基本公式

ビット演算以外でも、論理演算、集合論でも通用する。ここは暗記すべし。


基本演算

  • ~~x = x
    • 反転して反転したら元に戻る
  • x | 0 = x
  • x & 0 = 0
  • x ^ 0 = x
  • x | ~0 = ~0
  • x & ~0 = x
  • x ^ ~0 = ~x
    • ~0は1111..1
  • x | ~x = ~0
  • x & ~x = 0
  • x ^ ~x = ~0
  • ~0 = -1(符号付)
  • ~0 = 111..1


吸収則

  • x | (x & y) = x
  • x & (x | y) = x


ド・モルガンの法則

  • ~(x | y) = ~x & ~y
  • ~(x & y) = ~x | ~y


両辺にnot

  • x | y = ~(~x & ~y)
  • x & y = ~(~x | ~y)


ということは、

  • ~x | y = ~(x & ~y)
  • ~x & y = ~(x | ~y)


xorをand,or,notで書くと

  • x ^ y = (x | y) & ~(x & y)
  • x ^ y = (x | y) & (~x | ~y)
    • ド・モルガンの法則より。
  • x ^ y = (x & ~y) | (~x & y)
    • x ^ y = (x | y) & (~x | ~y)より、
      • 分配法則で、(~x | ~y)を分配。
    • = (x & (~x | ~y)) | (y & (~x | ~y))
      • 更に分配
    • = ( (x & ~x) | (x & ~y) ) | ( (~x & y) | (y & ~y) )
      • a & ~a = 0なので、
    • = (0 | (x & ~y)) | ((~x & y) | 0)
      • a | 0 = aなので、
    • = (x & ~y) | (~x & y)


xorの性質

  • x ^ (x ^ y) = y
  • ~x ^ y = ~(x ^ y)
  • ~x ^ ~y = x ^ y
    • xorの式に代入すると、ド・モルガンの法則で元に戻る。おもろい。


and,orをxorで表すと、

  • x | y = (x & ~y) ^ y
    • x | yを成分に分解すると、(x & ~y) ^ (x & y) ^ (~x & y)に分けられる。
    • ゴニョゴニョやると出る。サッパリしない証明。
  • x & y = (x | ~y) ^ y

半加算器,全加算器

半加算器は、xorすると、mod 2の足し算、andで桁上がりがわかるので、sはsum,cはcarryとして、

s = x ^ y
c = x & y


全加算器は、半加算器2個を使って下からの桁上がり(c-in)に対応する。

s = x ^ y ^ c-in
c = (x & y) & ((x ^ y) & c-in)

全加算器をいっぱい組み合わせると、

x + y = s + (c << 33)

が出来る。普段はキャリーを無視する。x86ならCFを見ればわかる。

加算

マイナス

  • -x = ~x + 1
  • -x = ~(x - 1)
    • 2の補数取り
  • -0 = 0
    • おもろい。


上から、

  • ~x = -x - 1
  • -~x = x + 1
  • ~-x = x - 1


論理式を足し算、引き算に分解。

  • x | y = (x & ~y) + y
    • x | y = (x & ~y) ^ yからだと思う。
  • x & y = (~x | y) - ~y
  • x & ~y = (x | y) - y


xor

  • x ^ y = (x | y) - (x & y)
    • x ^ y = (x | y) & ~(x & y)を、x & ~y = (x | y) - yにぶち込む。
    • = ( (x | y) | (x & y)) - (x & y)
      • 分配法則で分配
    • = ( ( (x | y) & x) | ( (x | y) & y)) - (x & y)
      • (a | b) & a = aから、
    • = (x | y) - (x & y)


足し算

  • x + y = x - ~y - 1
    • 上から
  • x + y = (x ^ y) + 2(x & y)
    • mod2足し算 + キャリーのビットシフト
  • x + y = (x | y) + (x & y)
    • xorの式から

マスク技

  • -00001000 = 11110000
    • 1ビット立てておいて、-すると左側マスクが出来る。[2-6]

比較技

  • sign(x) = (x > 0) - (x < 0)
  • sign(x) = (x >= 0) - (x <= 0)
  • cmp(x, y) = (x > y) - (x < y)
  • cmp(x, y) = (x >= y) - (x <= y)

猛烈に感動した。

比較述語[2-11]

比較した結果を「符号位置」に入れる事で分岐不要の式を作る。


例えば、x,y,zがゼロ以上かどうか。

~(x | y | z)

最終的にビットシフトすればいい。神杉。

オーバーフローの検出[2-12]

オーバーフローの検出なんて考えたこと無いw

_MAXの足し算について。

  • INT_MAX + INT_MAX = -2
    • INT_MAX << 1
  • INT_MIN + INT_MIN = 0

符号付足し算、引き算でのオーバーフローチェックは、オペランドの符号が同じなのに、結果の符合が逆になっちゃった場合を検出する。

  • ~(x ^ y) & ((x + y) ^ x)
    • 足し算。結果は符合位置に入る。

ビット演算では符合位置に結果を入れちゃうのが常套手段らしい。確かにソコ便利だよね。メモメモ。

便利そうな命令

  • nabs(x) = -abs(x)
    • 逆絶対値。完全RISC
  • nlz(x)
    • 先頭からのゼロの数を数える。完全RISC
    • RISCではbitcountをpopと言うみたい。わかりにくいな。

参考


まだまだ続く・・・はず。