Heavy Watal

ビット演算 — Bitwise operation

基本

きっちりサイズが定義されているものと、 下限だけが定義されてて環境依存のものがある。

符号あり(signed)型の場合、左端のビットが符号を司る。

// uint8_t
0b00000000 //    0
0b10000000 //  128
0b11111111 //  255

// int8_t
0b01111111 //  127
0b10000000 // -128
0b10000001 // -127
0b10000010 // -126
//
0b11111101 //   -3
0b11111110 //   -2
0b11111111 //   -1

0bbinary literal (C++14) の接頭辞

演算子 operator

// AND, OR, XOR
x & y
x | y
x ^ y

// NOT, complement of 1
~ x

// negation, complement of 2, (~x | 1)
- x

// shift
x << n
x >> n
x >>> n
// int8_t
x = 5   // 0b00000101
x & 1   // 0b00000001 =  1
x | 2   // 0b00000111 =  7
x ^ 3   // 0b00000110 =  6
~ x     // 0b11111010 = -6
- x     // 0b11111011 = -5
x << 1  // 0b00001010 = 10
x >> 1  // 0b00000010 =  2
x >>> 1 // 0b00000010 =  2

応用

符号反転 -x は、全ビット反転して1加えることに相当する (~x | 1) 。 つまり、符号反転して全ビット反転すると、1加えるのと同じ。

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

std::vector<bool>

std::bitset<N>

ビット数がコンパイル時定数

boost::dynamic_bitset<>

http://www.boost.org/doc/libs/release/libs/dynamic_bitset/dynamic_bitset.html

可変サイズ版bitset

find_first(), find_next(), is_subset_of() など便利な補助関数もあるが、速度的な最適化はされてないっぽいので、 実行速度がシビアな場面では普通に operator[] で自前ループを書いたほうがいいかも。 operator& とかも意外と遅い。