へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集

プログラミング

この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。

12月20日追記：
Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：）

はじめに

　　　　　　Y＾´　　 　 　 ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ !　｜ ｌ }´　　　　 〈
　　　　　　 〉 　　 変　　〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l　ｌ〈　　変　　/
　 　 　 　 〈　　　 態.　　 ∨, '／l| 　 ,.'-‐､｀/／｀7/　 ／''"´__　｜　ﾊ l丿　 態 　 {
　　　　　人）　　　! !　　　（／! 　|ヽ〈_　・.ﾉ〃 　〃 ／　 '／⌒ヾ.!　,'　!く　　 ! !　　（_
　ト､__／ 　 ヽ､_,.イ　 　 ／ｌ　ｌ　｜:::::::｀｀`/:::::／...´.. 　 //´｡ヽ　}! ,'　 !! )　　　　　／
ト'　　 　亦　　　,ｲ⌒ヽ/ 　 !l l !　l　し　　　Ｊ ::::::::::::::::::::｀`‐-<／ /　 ,'、｀Y´Τ｀Y
l　 　 　 夂　　 （ﾊ ヽ　ｌ i 　 ! l ',　!　　 , -―-､_　　　′::::::::::::: //!　Λ ヽ、ヽl
ヽ　　　　　 　 　 〉,＼　! i 　 ',.ｌ `、'､／_,. ―- ､_｀`ヽ､　 ι　 〃,'／!　ヽ、＼ ヽ、
　! 　 　 能　　 // ,' ｌヽ! ii　　',l 　∨＼'⌒ヽー-､ ｀ヽ､!　　 ／　ハ ﾉヽ._人_从_,. ＼
　|　　　 心 　 ｛　/ ,' ' ,! ｌl　　l`、 { ヽ'　＼　　 　 ヽ　 ' 　'´ 　 Λ ',}　　　　　 （ ＼
.丿　　 　 　 　 ∨ // ,',! l l　　l ヽ`、 ＼　 ＼　　　∨ 　 し ／!　∨　　変　　 ,ゝ､
∧ 　 　 / /　　 ヾノ //ｌ l　l　　l､_ヽ＼　＼ 　 ヽ　, '　　 ,.イ　｜ノ　 　 態 　 （ヽ
/ﾉ__　　ﾟ　ﾟ　　(⌒｀〃'j | l　 l 　 l　｀ヽ ｀ヽ､.ヽ _,.}'′ ,.イｌ　{　　| ヽ　　　! !　　 ,ゝ＼
/　/｀Y⌒ヽ/⌒　〃　ﾉ | l 　 l 　 l 　 } ヽ､._　}　ﾉ,.イ l　| !　!　　|　 ）_

競技プログラミングでは、アルゴリズム(どう解くか？)を考えること以外に、どう実装するか？も問われます。
通常、実装にかかる時間が短い方が得点が高く、実装の手間がかからない方法を取ることも重要になります。
この記事では、そんな手法の1つとして「bitを使った実装」をいくつか調べてまとめてみます。


普通のプログラミング言語には、整数型の変数に対するビット演算子(AND,OR,XOR,...)が定義されており、その変数の各ビットに対して演算を行うことができます。
これを利用すると簡単に、高速な演算処理や集合表現などが行えます。
以下、競技プログラミングで使える、使えそうなものを記したいと思います。

注意書き

  • プログラミング言語だけでなく、アーキテクチャ、プロセッサにも依存する可能性があるため、実行環境によって速度や挙動が変化する場合があります
  • ビット演算は魔術なので、使い過ぎると可読性が著しく落ち、自分にも他人にも厳しい変態的なコードになってしまう可能性があります

1.XORswap(値の交換)

ある変数aとbの値を交換したい場合に、一時変数を用意することなしにxor演算だけで交換できます。
(追記：同じ値の時はswapしないようにしないといけません引数のポインタが同じ値の時は、xorすると0になってしまうため、処理をしないようにしないといけません(コメント欄参照))

実装
#include <iostream>

/* //2016/11/1追記：コメント欄参照
void swap(int& a, int& b){
  //値が同じかどうかを確認(ポインタが同じ場合をはじく意味と、値が同じ場合は無駄なので処理省く意味)
  if(a != b){ b ^= a; a ^= b; b ^= a; }
}
*/

void swap(int *a, int *b){
  //ポインタの値が同じじゃないことを確認(同じだと0になってしまう)
  if(a != b){ *b ^= *a; *a ^= *b; *b ^= *a; }
}

int main(){
  int a = 1, b = 2;
  swap(a, b);

  std::cout << a << " " << b << std::endl;
  
  return 0;
}
参考

2.XORshift(擬似乱数生成)

xor演算とビットシフトのみから高速に生成できる擬似乱数です。
マラソンマッチなどで使えそうでしょうか。

実装
uint32_t xor128(void) { 
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123; 
  uint32_t t;
 
  t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
}

http://d.hatena.ne.jp/jetbead/20110912/1315844091

参考

3.FFT(ビット反転を使ったバタフライ演算)

FFTとは、離散フーリエ変換と呼ばれるものを高速に演算することができるアルゴリズムです。
そのまま計算するとO(n^2)になるところを、うまく分解・まとめあげを繰り返すことでO(nlogn)にすることができます。
その計算方法のバタフライ演算と呼ばれる部分に「ビット反転」を使った並び替えが使われています。

FFTは、多倍長の掛け算をO(nlogn)で実現できます。
http://homepage2.nifty.com/m_kamada/math/fftmul.htm#fftmul

実装

http://www.kurims.kyoto-u.ac.jp/~ooura/fftman/ftmn1_25.html#sec1_2_5

参考

4.Levenshtein距離(ビットパラレル法)

編集距離と呼ばれるものの一つで、2つの文字列について、最低何回挿入・削除・置換すれば同じ文字になるか、です。
通常のDPだと、それぞれの長さがnとmだとO(nm)の計算量がかかります。
しかし、各DPの行(または列)の状態をビットで保持、一回で計算でき、計算を高速化(O(floor(m/w) n)間違いましたO(ceil(m/w) n)でwは1単位のビット数(ワード長)で、32bitや64bitなどが入ると思います)することができます。

参考

5.部分集合列挙

nビットの整数型の場合、「n個の0か1を値に持つ配列」と見なすことができます。
値が1のビットを「集合の要素」とすると、変数を使った集合を表現でき、
0(=空集合)から1を足し続けることで、すべての部分集合(冪集合)を生成することができます。
例: n=3のとき、000,001,010,011,100,101,110,111

実装
#include <iostream>

typedef unsigned long long ull;

void print_bit(ull S, int n=64){
  for(int i=n-1; i>=0; i--){
    if(S>>i & 1) std::cout << 1;
    else std::cout << 0;
  }
  std::cout << std::endl;
}

void subset_generation(int n){
  for(ull S = 0; S < (1<<n); S++){
    print_bit(S, n);
  }
}

int main(){
  subset_generation(5);
  return 0;
}
参考

6.組み合わせ列挙

同様に、n個の要素のうち、k個を取り出す組み合わせというのも表現できます。
例: (n,k)=(4,2)のとき、0011,0101,0110,1001,1010,1100

実装
#include <iostream>

typedef unsigned long long ull;

void print_bit(ull S, int n=64){
  for(int i=n-1; i>=0; i--){
    if(S>>i & 1) std::cout << 1;
    else std::cout << 0;
  }
  std::cout << std::endl;
}

void subset_combination(int n, int k){
  ull S = (1ULL << k) - 1ULL;
  ull E = ~((1ULL << n) - 1ULL);
  while(!(S & E)){
    print_bit(S, n);
    ull smallest = S & -S;
    ull ripple = S + smallest;
    ull nsmallest = ripple & -ripple;
    S = ripple | (((nsmallest / smallest) >> 1) - 1);
  }
}

int main(){
  subset_combination(4, 2);
  return 0;
}
参考

7.Gray符号

部分集合列挙の時に、i番目に生成されたものとi+1番目に生成されたものの違いが1bitのみとなるような順番で列挙することができます。
例: n=3のとき、000,001,011,010,110,111,101,100

実装
#include <iostream>

typedef unsigned long long ull;

void print_bit(ull S, int n=64){
  for(int i=n-1; i>=0; i--){
    if(S>>i & 1) std::cout << 1;
    else std::cout << 0;
  }
  std::cout << std::endl;
}

void gray_code(int n){
  int N = 1 << n;
  ull G = 0;
  for(int i=0; i<N; i++){
    G = i ^ (i >> 1ULL);
    print_bit(G, n);
  }
}

int main(){
  gray_code(4);
  return 0;
}
参考

8.bitDP

整数型の変数で集合やパターンを表現できます。
したがって、そのような集合やパターンを状態として整数値で表現できるので、DPやメモ化が書きやすくなります。
プログラミングコンテストチャレンジブックでも章をたてて紹介されています。

実装

最短ハミルトン閉路
http://www.prefield.com/algorithm/graph/shortest_hamilton_path.html
他にも、グリッドのマスの状態など

参考

9.ビットボード

オセロやセルオートマトンなどの盤面のマスをビット集合で表現することで、整数型の変数1つか2つで状態を表現できます。
また、ループをまわさずに複数のビットを同時に演算することができる(ビットパラレル)ので、高速に処理ができます。
ゲーム木探索などで使えるでしょうか。

実装

ボードの状態を表示

#include <iostream>

typedef unsigned long long ull;

bool bitFlag(ull S, int y, int x){
  return S & (1ULL << (y * 8 + x));
}

void print_board(ull W, ull B){
  for(int i=0; i<8; i++){
    for(int j=0; j<8; j++){
      if(bitFlag(W, i, j)) std::cout << "o";
      else if(bitFlag(B, i, j)) std::cout << "x";
      else std::cout << ".";
    }
    std::cout << std::endl;
  }
}

int main(){
  print_board(0x1008000000, 0x0810000000);
  return 0;
}

(オセロ局面探索をしている先輩に聞いてみたところ、「白の位置と黒の位置」を保存する方法以外に「石の位置のシルエットと白の位置」を保存するという方法を教えてもらいました。まとめあげがしやすそうです。)

参考

11.空間充填曲線

空間充填曲線は、その空間を埋め尽くすように動く曲線で、平面グリッドの場合はすべての(x,y)を最低1回は通過するパスのことです。
有名なものに、ヒルベルト曲線やペアノ曲線、ムーア曲線などがあり、これらは再帰的な性質を持っています。
この動き(直進、回転)をビットを使うことで表現することができ、n回移動したときのマス目を高速に計算することができます。

参考

12.簡潔ビットベクトル

「簡潔データ構造」と呼ばれる、情報を理論限界近くまで圧縮しつつ定数時間で操作を行えるデータ構造を適用したビットベクトルです。
疎な巨大配列など、メモリを節約して保持することができます。
メモリの制限がきつい場合などに最終手段として使えるかもしれません。

実装

試しに書いてみたコード
https://github.com/jetbead/Prog/blob/master/succinct_bit_vector/sbvector.cc

参考

その他の参考文献

終わりに

この記事を書こうと思ったきっかけは、結構ちょくちょく見かけるけど、いったい他にどんなのがあるの？、と思って調べてみると意外にそういう視点でまとめられているものを見つけられなかったからです。
これらbitを使った実装は一手段にすぎませんが、知っているだけで有利になる場面もあるかと思います。
ビット演算などは実際にコードを書いて挙動を見てみないとよくわからなかったりすると思いますので、ぜひ実装してみてください。

　　　　　∧＿∧
　　　　　( ﾟωﾟ　)　おっしゃ！bitは任せろー
S&(1<<n)Ｃ□l丶l丶
　　　　　/　　(　　 )　やめて！
　　　　 （ノ￣と、　ｉ
　　　　　　　　しーJ