マジックナンバー0x03F566ED27179461の求め方とHD流のNLZ

の続きです。
siokoshouさんのところのマジックナンバー0x03F566ED27179461ULの求め方について、まだどこも書いていないみたいなので、昨日書いたのをちょこっと変更してみました。

posted with amazlet at 09.07.08

ジュニア,ヘンリー・S. ウォーレン
エスアイビーアクセス
売り上げランキング: 53370

では早速。

void MagicNum64(void)
{
    unsigned i, j, flg, val_h, val_l;
    
    val_h=val_l=0;
    flg=1;
    
    for (i=1; i<32; i++)
    {
        val_h = (val_h<<1) | flg;
        flg = 1 & ((val_h>>5) + (val_h>>0));  /* (6,1) */
    }
    val_l=val_h;
    for (; i<64; i++)
    {
        val_l = (val_l<<1) | flg;
        flg = 1 & ((val_l>>5) + (val_l>>0));  /* (6,1) */
    }
    val_l= (val_h<<(32-5))
           |(val_l>>5);
    val_h=val_h>>5;
    
    printf("0x%x%08x\n", val_h, val_l);
    getchar();
}

64bitな環境にないので32+32bitで計算するようにして、M系列を5次→6次に変更しました。
上記コードは(6,1)のパターンですが、(6,5,2,1)にすれば0x3731D7ED10B2A4Fが得られます。
このマジックナンバーでもテーブルを変更すれば使えるはず。

さて、昨日の書いたNLZは

unsigned nlzM(unsigned x) {
   if (x == 0) { return 32; }
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >>16);
   return 31 - ("\0\1\2\xf\x1d\3\x17\x10\x1e\x1b\4\6\xc\x18\x8\x11"
                "\x1f\xe\x1c\x16\x1a\5\xb\7\xd\x15\x19\xa\x14\x9\x13\x12")
               [0x5763e69U * (x - (x >> 1)) >> 27];
}

ですが、hacker's delightのnlz.cc*1を眺めていたら、これに似たコードがありました。

#define u 99
int nlz10(unsigned x) {

   static char table[64] =
     {32,31, u,16, u,30, 3, u,  15, u, u, u,29,10, 2, u,
       u, u,12,14,21, u,19, u,   u,28, u,25, u, 9, 1, u,
      17, u, 4, u, u, u,11, u,  13,22,20, u,26, u, u,18,
       5, u, u,23, u,27, u, 6,   u,24, 7, u, 8, u, 0, u};

   x = x | (x >> 1);    // Propagate leftmost
   x = x | (x >> 2);    // 1-bit to the right.
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >>16);
   x = x*0x06EB14F9;    // Multiplier is 7*255**3.
   return table[x >> 26];
}

テーブルは64個だけど、0避けのif文無し、掛け算の前処理 x - (x >> 1) も無い、そして新たなマジックナンバー0x06EB14F9の登場。
分岐が無いのと手順が1個少ないため、こっちのコードの方が速いです。
コメントのおかげで 0x06EB14F9 = 7*255^3 ということは分かりますが、何故これで求まるんですかね。。。

すごい、すごすぎる！hacker's delight！！
ちなみにこのNLZ10は僕の手元にあるハッカーのたのしみ（第3版）には掲載されていませんが、nlz.ccのコメントによるとfuture editionに掲載されるかも、ということらしいです。
ハッカーに少しでも近づきたい人は必携の書ですね、ハッカーのたのしみ(hacker's delight)は。

*1:hacker's delightのHDcode.zipの中にある