Bit演算チートシート

追記

これも参照すればいいと思うよ
すばらしいビット
(原本: https://github.com/keon/awesome-bits)

---

あの、アレ、なんだっけ？

(俺こんなのも知ってるぜ、という方は教えていただけれると喜びます)
#and[&] , or[|]
二項演算
両ビットが立っていたら真

 > 1011 0100
 > 1001 1010
[&]1001 0000

どちらかのビットが立っていたら真

 > 1011 0100
 > 1001 1010
[|]1011 1110

#xor[^]
両ビットが食い違ってたら真
割と有益

 > 1011 0100
 > 1001 1010
[^]0010 1110

#not[~]
単項演算。bitを反転する

 > 1011 0100
[~]0100 1011

#shift[<<][>>]
左辺のbitを右辺分だけずらす。
(1011 0100) << 2
1101 0000
(1011 0100) >> 2
0010 1101
左辺が負の場合、ちょっとよくないだろう
((-1)>>9の結果が何になるかご存知であろうか。あるコンパイラだと-1になる。この動作は未定義である(本の虫：シフト演算子))
x<<nはx*2^nと(マイナスとかオーバーフローとか考えなければ)同意義である。しかも早い
x>>nはx/2^nと(マイナスとかオーバーフローとか考えなければ)同意義である。しかも早い

#単項プラス[+x]
特に何もおこらない。identityな関数である。右辺値にするのに役立つかもしれない
+x → x

#単項マイナス[-x]
signedな数は 0~(n-1)のn個と(-1)~nのn個でできている
対応を取っていくと(0,-1) (1,-2) (2,-3)……(n-1,-n)のような具合になる
そして片方の数をビット反転させるともう片方の数になる
3) 0011 → -4)1100
-nの結果はn-1の反転 つまり~(n-1)となる

#加算[a+b]
加算器でググれ
xorとかandとかorで実装できるらしい。ただの２進数の筆算な気がしなくもない。詳しい人募集
#減算[a-b]
a+bの桁あふれを切ったものと等しいらしい
9-8 = 1 = 9+8 = 17 = 1(mod 16)
すごいね。詳しい人募集
#乗算
[乗算器]{http://ja.wikipedia.org/wiki/%E4%B9%97%E7%AE%97%E5%99%A8}でググれ
だんだん複雑になってくる。あなたはだんだんビット演算を使いたくなってきましたね？
（一般に過剰な最適化は避けるべきである。疲れるし、割とコンパイラが頑張ってくれるからだ）
詳しい人募集
#剰余算
詳しい人募集

#応用されるBit演算
ビット演算は様々なところで活躍したり悪用されたりしています。報告者募集

##オタマジャクシ[-~][~-]

単項マイナス[-x]
bitとしてみると -nの結果はn-1の反転 つまり~(n-1)となる

マイナスとnotを用いることでn-1やn+1を書くことができる
~-nは ~~(n-1) n-1と等しい
~-n == n-1
-~(k-1)は- -k k k-1=nより -~n→n+1
-~n == n+1
コードゴルフなどで用いられる
(n+1)*2:7文字-~n*2：５文字

##乱数(xorshift)
http://ja.wikipedia.org/wiki/Xorshift
そういう乱数生成アルゴリズムがある。早いらしい

##整数のswap
xorを用いてswapすることができる

(a:1011,b:0010)
a ^= b;//(1001,0010)
b ^= a;//(1001,1011)
a ^= b;//(0010,1011)

やってることは

a=(a^b)^(a^b^b)
b=(a^b)^b

である
テンポラリがいらない分ちょっと早いらしい。が、aとbが同じ変数だとバグる

(a:1011)
a^=a;(0000)
a^=a;(0000)
a^=a;(0000)

##バイトニックソートの一部計算 ( n+c*(n/c mod 2?-1:1) : c=pow(2,k))
c==pow(2,k)==(1<<k)

n/c mod 2 
 -> n/(1<<k) mod 2
 -> n>>k mod2
 -> nのk bit目(以下n[k])
n+c*(n/c mod 2?-1:1)
 ->n+c*(n[k]?-1:1)
 ->n[k]?n-c:n+c
 ->nのk bit目をxor
 ->n^(1<<k)

バイトニックソートでこの計算を使う場面がある

##あたり判定(モートン順序)
http://marupeke296.com/COL_2D_No8_QuadTree.html
自身がどの空間に属すかを判定するのに用いることができる

##JavaSsript:Floorとして扱う
http://naoyashiga.hatenablog.com/entry/2013/10/29/184914