Bitwise Tricks & Techniques - Darseinのプロコン日記

　この記事はCompetitive Programming Advent Calendar Div2012、20日目の記事です。(余談：そういえば本日2012/12/20は良い日ですね！)

はじめに

　今回はDonald.E.Knuth著”The Art of Computer Programming”のVolume4-1の前半パートであるBitwise Tricks & Techniquesで取り上げられているビット演算について記事を書きたいと思います。ただし、ここで取り上げられているものは必ずしも競技プログラミングにおいて実用的とは限りません。すでに関数として定義されているものはそれを使った方が実装量が減らせてよいと思います。なので、「ビット演算やべぇおもしれぇ！！」と思ってもらう一助となることを目指した読み物、という感覚で読んでいただけると幸いです。

　今回はC++言語を基本としてコードを紹介しますが、だいたい普通の言語なら実装されているであろうビット演算しか使いません。基本的にはAND、OR、XOR、NOT、LEFT(RIGHT) SHIFT、+、-、*があれば十分です(本の中ではアーキテクチャレベルでbit matrix演算が1ステップで出来ることが想定されてたりするMMIXというやばい言語が使われています)。また、x番目のビット、というときは特に断りがない限り右から0-originで数えて下さい。例えば(01000)は3番目のビットが立っています。unsigned long longをullと略記します。

　次節は本のあらまし、そのまた次節はビット演算の基礎で、本の内容には直接関係ないので興味のない方は読み飛ばしてもらって構いません。

KnuthとThe Art of Computer Programming

　Donald Ervin Knuthは単文では紹介しきれないほど偉大な業績*1をお持ちの計算機科学者です。プログラミングコンテストに参加している方なら文字列検索アルゴリズムであるKMP(Knuth-Morris-Pratt)法などで名前を聞いたという方も多いと思います。The Art of Computer ProgrammingはKnuth先生が自らライフワークと宣言するほど力を入れている著書で、現在4巻の分冊4までが出版されています(7巻まで出す予定らしい)。濃い内容で演習問題も~~鬼畜の如く~~充実していることでも有名です。

　今回紹介するVolume4-1は論理関数に関する話を取り扱ったもので、前半がビット演算、後半がBDD(Binary Decision Diagram)について記されています。数え上げお姉さん動画で有名になった(？)ZDDも載っているので興味がある方は手に取ってみるとよいでしょう。今回は前半のビット演算からトピックを持ってきて紹介したいと思います。

ビット演算

　そもそもコンピュータは内部では0か1かの二値(=ビット)ですべての情報を扱っています。二値を扱う演算は論理演算と呼ばれ、全部で $2^{2^2}$ 通り考えることができます。

　このビットを複数個組み合わせたものを見ることでコンピュータは様々な情報を表現します。たとえばC++言語の通常の整数型では、32ビットを利用して $-2^{31}$ 〜 $2^{31}-1$ までの整数を表現しています。ビット演算とは、このようなビットのまとまりに対する操作を行うものです。つまり整数型では32ビットを一気に扱う操作となります。

　これはよくよく考えるとものすごいことで、論理演算を32回行わないといけないこともまとめて処理することで1回で済む、つまり32倍高速化できるわけです(その効力は去年のxhl_kogitsuneさんの記事”悪い子のためのビットベクターによる定数倍高速化”等を参照)。このように、ビット演算を駆使することで計算を効率的にしたり、情報をわかりやすく表現したりすることで、より幅の広いプログラムを書くことができます。

　情報をわかりやすく表現する、という一例として、集合の表現があります。これはi番目のビットに1が立っていればi番目の要素が集合に含まれている、と解釈するもので、プログラミングコンテストチャレンジブック(第2版が好評発売中です！やべぇ！)などでもわかりやすく紹介されています。

　この表現の凄いところは最小完全ハッシュ関数になっている上にsubset→supersetの順に昇順になっており、しかもデコードせずとも様々なクエリをO(1)で処理できるなど挙げればキリがありません。あまり注目されていない性質な気もしますが、例えば順列の最小完全ハッシュ関数としてよく知られているもの(http://www.ic-net.or.jp/home/takaken/nt/slide/hash.html)は愚直に構築するとO( $n^2$ )かかってしまいます*2し、コードのまま操作する方法も考案されていないようなので、操作しようとするとデコード→操作→エンコードというように、一度解凍しないと使えないです。集合のように自由にはいきません。このように、集合のビット表現は非常に面白い性質を持っていて、プログラムで集合を扱うときにとても便利です。

　以上、ビットを駆使するメリットの一部を紹介しましたが、他にもここでは書ききれないほどたくさんあります。今年2日目のPhylloさんの記事"へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集"なども見てみるとよいでしょう。ビット演算に興味が湧いてきたところ(？)で、いよいよ本題の本の内容に入ります。

rightmost bit

　xのrightmost bitとは、xの一番右に立っているビットのことです。例えばx = (10100)だと右から2番目のやつですね。これを取り出す簡単な式は有名で、y=x&-xです。でも、これはあくまでy=(00100)というのを手に入れただけで、”2番目”という情報はこれだけでは得られません。つまり、直接yに2を代入してほしいこともあります。これを $\rho$ とする(すなわち、最右は $\rho$ 番目のビット)と、どうすれば $\rho$ を求められるでしょう？普通にやるとO(n)かかってしまいます。
　これには2通りの方法が紹介されています。1つ目は、”magic mask”を利用する方法。“magic mask”とは以下のようなものです。

　 $\mu_0$ = (…010101010101010)
　 $\mu_1$ = (…011001100110011)
　 $\mu_2$ = (…000111100001111)
　 $\mu_3$ = ……

　すなわち $\mu_i$ では $2^i$ 個の連続した0と1が交互に現れます。この“magic mask”は以降も頻繁に現れます。これを使うと以下のような式で $\rho$ を書き下せます([A]はAが真なら1,偽なら0の値を取ります)。

　 $\rho$ = [x & $\mu_0$ == 0] + 2[x & $\mu_1$ == 0] + 4[x & $\mu_2$ == 0] + …

$\rho$ の2進数表示におけるi番目のビットが1かどうか、を $\mu_i$ でマスクすることによって調べているわけです。よって、64bitなら以下のようにコーディングできます。

 int right_num(ull x){
  ull M[6] = {0x5555555555555555, 0x3333333333333333,
	      0x0f0f0f0f0f0f0f0f, 0x00ff00ff00ff00ff,
	      0x0000ffff0000ffff, 0x00000000ffffffff};
  int rho = 0, pow = 1;
  x = x&-x;
  for(int i=0;i<6;i++){
    if(!(x&M[i]))rho += pow;
    pow <<= 1;
  }
  return rho;
}

これで、O(logn)まで落とせました。
　2つ目の方法ははっきりいうと埋め込みです。

　 $\rho$ = decode[( (a*(x&-x) )mod $2^{64}$ )>>58]

とすると、例えばa = 0x03f79d71b4ca8b09 と以下のdecodeテーブルでO(1)で $\rho$ が求まります。ullを用いるとオーバーフローすると勝手にmod $2^{64}$ と同じことになるので便利です。decodeの[　]の中の部分はハッシュ関数のようになっているわけです。

  int decode[64] = {  0, 1,56, 2,57,49,28, 3,61,58,42,50,38,29,17, 4,
                     62,47,59,36,45,43,51,22,53,39,33,30,24,18,12, 5,
                     63,55,48,27,60,41,37,16,46,35,44,21,52,32,23,11,
                     54,26,40,15,34,20,31,10,25,14,19, 9,13, 8, 7, 6 };

aは何でもよいわけでなく、8bitずつスライドさせていって出てきた2進列が全て異なる必要があります。この制約を守ることでハッシュ関数の全単射性を保っているのです。

leftmost bit

　leftmost bitは一番左に立っているビットです。y番目に立っているとすると、y=⎿lgx⏌です(ただし、xは正整数)。以下のコードでO(logn)で求まります。

  int left_num(ull x){
    int lam = 0, pow = 32;
    for(int i=0;i<6;i++){
      if(x>>pow){
        lam = lam + pow; x >>= pow;
      }
      pow >>= 1;
    }
    return lam;
  }

上位powビットがすべて0なら下位powビットに最左ビットがあり、0でないなら上位powビットのどこかに最左ビットがある。二分探索ですね。

sideways addition

sideways additionとは、所謂popcountと同じです。つまり、立っているビットの数のことです。xのsideways additionを $\nu$ とおくと、

　 $\nu$ = $x_{n-1}$ + … + $x_1$ + $x_0$

です。簡単な方法として、rightmost bitを消していく方法があります。つまり、

  res = 0;
  while(x){x = x&(x-1); res++;}

これはxがsparse、すなわち立っているビットが少ないとき有効です。逆にdenseなときは、

  res = 64;
  while(x<-1ULL){x = x|(x+1); res--;}

などとすればよいです。ullだと-1ULLは $2^{64}-1$ になります。
　しかしこれだと結局最悪時O(n)です。これは以下のようにすると改善できます。

  ull popcount(ull x){
    x = x-((x>>1)&M[0]);           //2bit毎のpopcountが32個並ぶ
    x = (x&M[1])+((x>>2)&M[1]);   //4bit毎のpopcountが16個並ぶ
    x = (x+(x>>4))&M[2];           //8bit毎のpopcountが8個並ぶ
    return (0x0101010101010101*x)>>56;  //8個を足した数を返す
  }

分割統治法の要領で、小さい部分問題からより大きい部分問題の答えを求めています。 $2^{i+1}$ ビット毎のpopcountを出すために(x&M[i])+((x>> $2^i$ )&M[i])すればよいのは手でやってみるとわかると思います。よって、1,3行目もそのように書けばよいのですが、ここはコードのように書くことで演算回数(式中の+とか&とか>>とかの個数)を減らすことができ、最適化されています。returnのところがなぜこうなるのかは、筆算のように書き下してみるとわかると思います。

bit reversal

　bit reversalはビットを逆順にする操作です。これは局所的なreverseを繰り返し、範囲をどんどん広げながら行うことでできます。

  ull reverse(ull x){
    x = (x>>1)&M[0] | (x&M[0])<<1;
    x = (x>>2)&M[1] | (x&M[1])<<2;
    x = (x>>4)&M[2] | (x&M[2])<<4;
    x = (x>>8)&M[3] | (x&M[3])<<8;
    x = (x>>16)&M[4] | (x&M[4])<<16;
    x = (x>>32)&M[5] | (x&M[5])<<32;
    return x;
  }

これもsideways additionと同じような分割統治法とみることができます。

bit swap

　bit swapは、i番目のビットとj番目のビットを入れ替える操作です(i>j)。δ=i-jとすると、

y = (x>>δ)& $2^j$ , z = (x<<δ)& $2^i$ , x = (x&(~( $2^i$ | $2^j$ ))|y|z

でできます。yにはxのjビット目が立っているときiビット目が立っているものが、zにはxのiビット目が立っているときjビット目が立っているものが入ります。最後にxのi,jビット目を0にしたものとy,zのORをとればＯＫです。でもこれだと普通すぎてつまらないです。XORをつかうともっと短く出来ます。

  ull swap(ull x, int i, int j){
    ull d = i-j, y = (x^(x>>d))&(1ULL<<j);
    return x^y^(y<<d);
  }

これはXORの特性を使っています。XORは異なるビットのときのみ1を返します。すなわち、 $x_i$ ≠ $x_j$ のときだけ、yのjビット目が立っています。さらに、1とXORをとるとそのビットは反転します。よって、yのjビット目が立っているとき(= $x_i$ ≠ $x_j$ のとき)、xのi番目のビットとj番目のビットが反転します。 $x_i$ ≠ $x_j$ なので、これで $x_i$ と $x_j$ が入れ替わったことになるのです。 $x_i$ = $x_j$ のときは何もしませんが、同じなので入れ替える必要はありません。何もしなくてよいのです。

Application to Data Structure

　プロコン勢の皆さんおなじみのデータ構造にheapがあります。これは格納順に番号を付けていくと以下のようになります(右は番号を2進数にしたもの)。

　これと似たようなものとしてさらにsideways heapというものがあり、これは以下の図のようなものです。

　これはin-order(通りがけ順)に対応するように番号付けするものです。注意すべき点は、すべての頂点を参照するためにはn(図ではn=10)を越えた番号の頂点も途中で現れることがある、という点です。この2つのヒープは面白い違いがあり、要素が無限個あると仮定すると、通常のheapは根が定まる(1)のに対して葉は定義できませんが、逆にsideways heapは無数の葉がある(奇数番号)が根がありません。
　それぞれのヒープ上の頂点xからみた関係クエリは以下のように行えます。k=x&-xです。

　このsideways heapを考えることでなにが嬉しいかというと、nearest common ancestor(所謂LCA、最近共通祖先)を任意の有向森に対して求めることができたり、priority queueとして使えたりします。この辺が面白いところなのですが、~~時間上~~紙面上割愛させていただきます。興味のある方は読んでみて下さい。

おわりに

　長くなってしまい＆説明不足でごめんなさい。しかしBitwise Trick & Techniquesで取り上げられているトピックはまだまだたくさんあります(一度に複数箇所操作したりとか、他の応用の話とか)。興味を持っていただいた方は是非原著を読んでみるとよいと思います。
　明日の記事担当はtomerunさんとtouyoubuntuさんです。楽しみですね！

*1:代表的なものでは、TeX・METAFONT開発、チューリング賞(1974)、フォンノイマンメダル(1995)、京都賞(1996)など

*2:見かけないですがfenwick木を用いればO(n logn)にできるはずです。まあハッシュ関数値が実用的に機能するのはn=20くらいがせいぜいなのであまり影響は大きくないと言えなくもないです