ビット演算(集合)テクニック
Latest Author
こちらのページも参考
http://graphics.stanford.edu/~seander/bithacks.html
- 1のビット数をカウントする (population count, popcount)
- 特別な命令が無いCPUにおいては、こちらのアルゴリズムを使用すると速い
http://www.mwsoft.jp/programming/java/java_lang_integer_bit_count.html
言語や環境によっては事前に用意されていることがある。- Javaの場合、標準ライブラリの
Integer.bitCount
- gccの場合、
__builtin_popcount
- MSVCまたはclangの場合、intrin.h をインクルードして
__popcnt
- Javaの場合、標準ライブラリの
- $A \setminus B$(差集合)を計算する。(Aにだけ立ってる1のビットだけ残す)
A & ~B
もしくは(A|B) xor B
として計算できる。
1つ目のコードは$A \setminus B = A \cap \overline B$、2つ目のコードは$A \setminus B = (A \cup B)\ \triangle\ B$ であると言っている。