「2^a を与えられたときに a を求める(ただし 1≦ a ≦9)」記事へのコメント

別解

[t-nissie (8647)]

if (x.eq.1) return 0
if (x.eq.2) return 1
if (x.eq.4) return 2
if (x.eq.8) return 3
（中略）
if (x.eq.512) return 9
stop 'illegal x'

こっちの方が見通しがよいしx=1に対応できますが、
ぼくがなにか勘違いしているのかな。

--
love && peace && free_software
t-nissie

Re:

[TarZ (28055)]

　合っていると思います。が、元々の問題の要請が、なるべくループやlogを使わない（でもってできればステップも減らしたい）なのです。
　ということで、1, 2, 4, ... 512 の完全最小ハッシュを作る、というのが最小の解のようです。（乗算x1, ビットシフトx1, インデックスメモリ参照x1）

Re:

[t-nissie (8647)]

> ということで、1, 2, 4, ... 512 の完全最小ハッシュを作る、というのが最小の解のようです。

これが題意か。納得。しかし、

>（乗算x1, ビットシフトx1, インデックスメモリ参照x1）

ここまで小さくできないです。これがぼくの限界か（32bit限定だし）：

#define func1to9(x) ( 9 - (2271560481U*(x>>1)*(x>>1)*(x>>1)*(x>>1) >> 28) )
#define func0to8(x) ( 8 - (2271560481U*x*x*x*x >> 28) )

0≦a≦8のほうが綺麗に書けるから、わざわざ1≦a≦9にしているのを使っていないのか…

--
love && peace && free_software
t-nissie

Re:別解

[TarZ (28055)]

　今見つかっている最小のハッシュ関数はこれですね。乗算とシフト、11バイト+終端1バイトのテーブルを使います。どうやって求めたのかは私も解りません。

"\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28];