Re: 一番右端の立っているビット位置を求める「ものすごい」コード

algorithm

　http://d.hatena.ne.jp/siokoshou/20090704#p1
すごいなあ。いろいろ応用が利きそう。
うろ覚えながら M 系列実装してみる。とりあえず 6bit目と 1bit目の出口をフィードバックしてみる。

def M(n, q = 6, p = 1):
    nm = 2**n-1
    m = [0] * nm + [1]
    for j in xrange(nm-n):
	for i in xrange(nm):
	    m[i] = m[i+1]
	m[nm] = m[nm - q] ^ m[nm - p]
    return m

N=6

m = M(N)
bit="".join(map(lambda x: str(x), m))
print bit
print hex(int(bit, 2))

0000001111110101011001101110110100100111000101111001010001100001
0x3f566ed27179461L

なんか記憶がうっすらだけれども一応出たみたい。

弾さんところで frexp使って出してるコードがあって、なるほど〜とか思ったんだけど、よーく考えてみたら、この場合 n & -nはいらない。さらに直接ビットパターンからひっぱりだすようにしてみたけど、

int ntz_fltexp(U64 n){
    union {
	int i;
	float f;
    } u;
    if ( n == 0 ) return 64;
    u.f  = n;
    return (u.i >> 23) - 127;
}

まあまあ、という程度にしか早くならなかった(Pentium4 2.40GHz/ Linux2.6.24-23)

 ntz_frexp: 7.28352s
ntz_fltexp: 4.63627s

ちょこざいな、だった。