ビット演算メモ
ハッカーのたのしみ読んでます。実はこの本、「解説が殆ど無い」。提示されているのは式のみ。後は自分で探るしかないのだ・・・メモメモ。
記号は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)
- x ^ y = (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)
- 足し算。結果は符合位置に入る。
ビット演算では符合位置に結果を入れちゃうのが常套手段らしい。確かにソコ便利だよね。メモメモ。
参考
- ハッカーのたのしみ
- パタヘネ(上)
- MIPSの理解に。半分くらいまで読んだ。
- プログラマの数学
- 栢木先生の基本情報技術者教室
- 論理演算 - Wikipediaあたりを巡ったところ。
まだまだ続く・・・はず。