2014-05-06-01-閑話休題：最左の０ビットを探す

>> Site top >> weblog >> 月別アーカイブ >> 2014年05月のlog >> 2014-05-06-01-閑話休題：最左の０ビットを探す

最終更新日付：2014/05/06 23:50:00

閑話休題：最左の０ビットを探す

2014 年 05 月 06 日

Twitter で、「最も左にある０のビットを探すにはどうしたらいいだろう」と書いている方がいらっしゃったので、自分なりに考えてみることにした。最初は C で書いて、それを Common Lisp に持っていく。つもり。

　

自分が考えた戦略は、基本的に以下の通り。

1. 与えられた x の「それより大きな最小の２の羃乗」を求める。これを z とする。
2. z から 1 を引いて x との排他的論理和を取る。これで、x で 0 だったビット位置だけが全て 1 であるような値が得られる。これを z に代入。
3. z の「それより大きな最小の２の羃乗」をもう一度取って、それを 1 ビット右にシフトする。これが答え。

さて、問題は「それより大きな最小の２の羃乗」をどうやって求めるか、だ。「ハッカーのたのしみ」という本には、「x 以上で最小の 2 の羃乗を求める」コードとして以下のようなものが紹介されている。

unsigned clp2(unsigned x) {
    x = x - 1;
    x = x | (x >>  1);
    x = x | (x >>  2);
    x = x | (x >>  4);
    x = x | (x >>  8);
    x = x | (x >> 16);
    return x + 1;
}

　

今回は「x 以上で」ではなく「x より大きな」最小の 2 の羃乗を求めたい。上記の clp2 関数に 2 の羃乗であるような値を与えると同じ値が返されるため、上記のコードを以下のように改変した。

unsigned int next_ceiling( unsigned int x ) {
    unsigned int z = x - 1;
    z = z | (z >>  1);
    z = z | (z >>  2);
    z = z | (z >>  4);
    z = z | (z >>  8);
    z = z | (z >> 16);
    z = z + 1;
    if( z == x )
        z = z << 1;
    return z;
}

　

この時点で「分岐もループもなし」という（個人的に暗黙の）目標は潰えたわけだ。そして色々な前提があることはさておき、これを利用した get_leftmost_zero は以下のようになるだろう。

unsigned int get_leftmost_zero( unsigned int x ) {
    unsigned int z;
    z = next_ceiling( x );
    z = z - 1;
    z = z ^ x;
    z = next_ceiling( z );
    z = z >> 1;
    return z;
}

　

この get_leftmost_zero、与えた数値に対して「最左の 0 のビット位置にだけ 1 が設定された値」を返してくる。試しに 45（ 101101 ）を与えてみると、16（ 10000 ）が返ってくる。ひとまず大丈夫なようだ。

で、これを Lisp コードに落とし込んでみようと思ったものの、そもそも next_ceiling が 32 ビット整数値にロックインしてしまっている。なのでおそらく Common Lisp では fixnum に対してしか動作しないだろう。さらに言えば、64 ビット版の Common Lisp 実装では全ての fixnum に対して正しく動作するわけではないだろう。そんな悲しい留保事項はあるにせよ、やってみたのが以下のコード。

(defun next-ceiling (x)
  (let ((z (1- x)))
    (setf z (logior z (ash z  -1)))
    (setf z (logior z (ash z  -2)))
    (setf z (logior z (ash z  -4)))
    (setf z (logior z (ash z  -8)))
    (setf z (logior z (ash z -16)))
    (incf z)
    (when (= z x)
      (setf z (ash z 1)))
    z))

(defun get-leftmost-zero (x)
  (let ((z (next-ceiling x)))
    (decf z)
    (setf z (logxor z x))
    (setf z (next-ceiling z))
    (setf z (ash z -1))
    z))

　

さすがにこれは（C からの単純置き換えなので）格好悪いかもしれない。Lisp っぽい書き方がお好みの向きには以下のようにすれば良いのだろうか。

(defun get-leftmost-zero (x)
  (ash (next-ceiling (logxor x (1- (next-ceiling x)))) -1))

　

なんにせよ、ちゃんと fixnum 対応するにはまだコードの修正が必要だと思う。書籍から拝借してきた clp2 が自分にとっては結構マジカルなので、そこまではやり切れなかった。無責任にも直感ベースで修正するなら、以下のように１行追記してやれば 64 bit 環境でも fixnum に対してはおおむね動作するようになる気がする（あくまで直感）。

(defun next-ceiling (x)
  (let ((z (1- x)))
    (setf z (logior z (ash z  -1)))
    (setf z (logior z (ash z  -2)))
    (setf z (logior z (ash z  -4)))
    (setf z (logior z (ash z  -8)))
    (setf z (logior z (ash z -16)))
    (setf z (logior z (ash z -32)))    ; add
    (incf z)
    (when (= z x)
      (setf z (ash z 1)))
    z))

　

あと、fixnum という制限を取り除いて integer 全てに対して正しく動作させるには‥‥‥多分ループが必要になるだろう。分岐もループも不要な、カリカリにチューニングされたコードというのは大抵（C で言うならば）int のビット幅とかに特定の前提を置いているものだ。その手の文化で書かれたコードを Lisp に持っていくのはそもそも難しいかもしれない‥‥‥というわけで中途半端になりましたが、何かの参考に、あるいは苦笑いのネタにでもなれば幸いです。

　

コメント

このページにコメントする

　

このページのタグ

Page tag : Common Lisp

　

　

---

Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.