ビット演算まとめ

典型的な8bitの整数4つについて、各種ビット演算の結果を二進法で示す。

	例1	例2	例3	例4	説明
b	01010000	10111011	00000000	11111111	元の数値
~b	10101111	01000100	11111111	00000000	NOT, ビット反転
-b	10110000	01000101	00000000	00000001	NEG, 符号反転
m = b ^ (b - 1)	00011111	00000001	11111111	00000001	b - 1 == (b ^ m) となるマスク
n = b ^ (b + 1)	00000001	00000111	00000001	11111111	b + 1 == (b ^ n) となるマスク
b & -b	00010000	00000001	00000000	00000001	下位から探して最初の1
b & (b - 1)	01000000	10111010	00000000	11111110	下位から探して最初の1を消す
b - 1	01001111	10111010	11111111	11111110	下位から探して最初の1を0にし、 それより下位のビットを1にする
b + 1	01010001	10111100	00000001	00000000	下位から探して最初の0を1にし、 それより下位のビットを0にする
(b ^ (b + 1)) / 2	00000000	00000011	00000000	11111111	最下位からの連続した1
~b & (b + 1)	00000001	00000100	00000001	00000000	下位から探して最初の0

同じ結果を得るのにも色々な方法があり、速度や可読性のために使い分ける。
特にb - 1 や-b は、よく使われる重要な筋。

m := b ^ (b - 1)
n := b ^ (b + 1)

-b = ~b + 1 = ~(b - 1) = b ^ ~m

b - 1 = b ^ m
~b + 1 = ~(b ^ m) = ~(b - 1)

b + 1 = b ^ n
~b - 1 = ~(b ^ n) = ~(b + 1)

~(b ^ m) = ~b ^ m = b ^ ~m

b & (b - 1) = b & (b ^ m) = b & ~m

b & (~b + 1) = b & ~(b - 1) = b & ~(b ^ m) = b & m = b & -b

~b & (b + 1) = ~b & ~(~b - 1) = ~b & (b ^ n) = ~b & n = ~b & -~b

b & (b - 1) は、bが2の冪かどうかの判定に使える。
ネタ元は、http://d.hatena.ne.jp/issei_y/20101212/1292138815,http://homepage1.nifty.com/herumi/adv/bbslog/bbs9.htmlの427。