ビット演算（集合）テクニック

Latest Author anta /Date 2015-09-12 04:46:34 / Views 3017
0 (Favした一覧ページはユーザーページから)
こちらのページも参考 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
$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$ であると言っている。