ryamadaのコンピュータ・数学メモ

2012-11-10

ブール演算のビット毎の演算のテクニック:ぱらぱらめくる『クヌース本4.1』

ブール演算ブール関数 R ぱらぱらめくるシリーズ

ブール演算・ビット毎演算を用いて、色々な効率化・高速化アルゴリズムがある。その例が以下に挙げられている
複数の情報、を詰め込む・へばらす
- 2012年11月10日を20121110と表すことを考える
  - 年が２
  - 年を構成する４つの数字を６桁左へシフトして
  - 月を構成する２つの数字と併せ
  - できた６つの数字列を８桁左へシフトして
  - 日を構成する２つの数字と併せて
  - 結局８つの桁の数字にしている
- これを２進法で行うには $x << k = \lfloor 2^k x \rfloor$ : kビット左へシフトと、 $x >> k = \lfloor 2^{-k} x \rfloor$ : kビット右へシフトとを使えばできる
ビッグエンディアンとリトルエンディアン・右端/左端のビットの扱い
- １を加えたり引いたりするときには最下位桁に働きかけて、繰り上がり・繰り下がりがある。そんなときの技
べき集合の取り扱いに使う
- 全桁の和は要素数を表す(横方向の加算)
ビットの反転
- $(x_1,x_2,...,x_k) \to (x_k,x_{k-1},...,x_1)$ はマジックマスクで
ビットの交換、置換
- $(x_1,...,x_i,...,x_j,...) -> (x_1,...,x_j,...,x_i,...)$ もマジックマスクの応用
分割区域での作業
多くのバイトで並行して作業
長大語
下界
有向グラフへの応用
データへの応用
- データ表現への応用
- データ構造への応用
画像
- ビットマップ画像
- 塗りつぶし・ラスター画像
分岐なし計算
MOR,MXORのさらなる応用
双曲線平面のセル