ドキュメント
Computer Science
アルゴリズム
最適化アルゴリズム
Bit Manipulation

Bit Manipulation

ビット操作(そうさ) 技法(ぎほう) - ビット演算(えんざん) を利用(りよう) してアルゴリズム性能(せいのう) を最適化(さいてきか) 。

一般的なアルゴリズム/応用と技法の対照表

アルゴリズム/応用(おうよう)技法(ぎほう) 1 (奇偶(きぐう) )技法(ぎほう) 2 (取得(しゅとく) )技法(ぎほう) 3 (1設定(せってい) )技法(ぎほう) 4 (0設定(せってい) )技法(ぎほう) 5 (切替(きりかえ) )技法(ぎほう) 6 (最右(さいう) 1消去(しょうきょ) )技法(ぎほう) 7 (最右(さいう) 1取得(しゅとく) )技法(ぎほう) 8 (計数(けいすう) )
暗号学(あんごうがく) (SHA/MD5)✓✓✓✓
IP/サブネットマスク✓✓✓✓
Bloom Filter✓✓✓
N 皇后問題(クイーンもんだい)✓✓✓✓✓
チェス盤(ちぇすばん) ゲーム状態(じょうたい)✓✓✓✓
グレイコード生成(せいせい)✓✓✓
権限(けんげん) システム✓✓✓
ハミング距離(きょり)✓✓
XOR 暗号化(あんごうか)✓
Fenwick Tree✓✓
Bitmap 操作(そうさ)✓✓✓✓
圧縮(あっしゅく) アルゴリズム (LZW)✓✓

基本ビット操作技法

  1. 奇偶判定(きぐうはんてい) (n & 1) == 0
  2. 第(だい) i ビットを取得(しゅとく) (n >> i) & 1
  3. 第(だい) i ビットを 1 に設定(せってい) n | (1 << i)
  4. 第(だい) i ビットを 0 に設定(せってい) n & ^(1 << i)
  5. 第(だい) i ビットを切替(きりかえ) n ^ (1 << i)
  6. 最(もっと) も右(みぎ) の 1 を消去(しょうきょ) n & (n - 1)
  7. 最(もっと) も右(みぎ) の 1 を取得(しゅとく) n & (-n)
  8. 二進数(にしんすう) 中(ちゅう) の 1 の個数(こすう) を計算(けいさん)
Cache