ビット演算 — Bitwise operation
https://github.com/heavywatal/scribble/blob/master/cxx/bitwise.cpp
基本
型
きっちりサイズが定義されているものと、 下限だけが定義されてて環境依存のものがある。
https://github.com/heavywatal/scribble/blob/master/cxx/sizeof.cpp
- 1byte == 8bits
sizeof(char)
== 1sizeof(bool)
>= 1sizeof(int)
>= 4sizeof(uint32_t)
== 4<cstdint>
sizeof(uint128_t)
== 16<boost/multiprecision/cpp_int.hpp>
符号あり(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
0b
は
binary 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
// assuming 8-bit
x = 5 // 0b00000101
x & 1 // 0b00000001 = 1
x | 2 // 0b00000111 = 7
x ^ 3 // 0b00000110 = 6
~ x // 0b11111010 = -6 or 250u
- x // 0b11111011 = -5 or 251u
x << 1 // 0b00001010 = 10
x >> 1 // 0b00000010 = 2
<<
は右から0を詰めて左端を捨てるunsigned
に対する>>
は左から0を詰めて右端を捨てるsigned
の負数に対する>>
は未定義だが、だいたい左端をコピーして右端を捨てる(i.e., 符号を維持しつつ2で割る)- 8-bit型に対する操作が必ずしも8-bitで返ってくるとは限らないし、
暗黙の整数型は大概32-bitとかなので、両辺とも明示的に型を指定するほうが安心。
特に上位ビットも変化する
~
や-
を使って比較するときは要注意。
応用
符号反転 -x
は、全ビット反転して1加えることに相当する (~x | 1) 。
つまり、符号反転して全ビット反転すると、1加えるのと同じ。
x = x + 1
x += 1
++x
x = -~x
std::vector<bool>
- 特殊化されているため普通のSTL vectorではない
- 省メモリ
- イテレータあり e.g.,
std::next_permutation()
data()
メンバが無い。つまりナマのビット列としてアクセスできない?
std::bitset<N>
- https://en.cppreference.com/w/cpp/utility/bitset
- https://cplusplus.com/reference/bitset/bitset/
- https://cpprefjp.github.io/reference/bitset.html
ビット数がコンパイル時定数
boost::dynamic_bitset<>
https://www.boost.org/doc/libs/release/libs/dynamic_bitset/dynamic_bitset.html
可変サイズ版bitset
find_first()
, find_next()
, is_subset_of()
など便利な補助関数もあるが、速度的な最適化はされてないっぽいので、
実行速度がシビアな場面では普通に operator[]
で自前ループを書いたほうがいいかも。
operator&
とかも意外と遅い。