Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

Bit演算チートシート

More than 3 years have passed since last update.

追記

これも参照すればいいと思うよ
すばらしいビット
(原本: 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<<nx*2^nと(マイナスとかオーバーフローとか考えなければ)同意義である。しかも早い
x>>nx/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で実装できるらしい。ただの2進数の筆算な気がしなくもない。詳しい人募集

減算[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より -~nn+1
-~n == n+1
コードゴルフなどで用いられる
(n+1)*2:7文字-~n*2:5文字

乱数(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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away