« OS自作入門 5日目 | Main | 今日の読書 »

2006.09.28

先頭から0を数える

ハッカーのたのしみ 5-3から。

先頭から続く0を数えるのは、本質的に2を底とするlog関数。上手く使うと
指数分布するランダム関数が作れる。

・浮動小数点に置き換えて指数部をとる
 →この発想は絶対にでてこない。思いついた奴天才。

・if(x<=0x00FFFFFF)の代わりに、if(x>>24)が使える。
 →比較(減算)がbitシフトになるだけでなく、命令中に大きな即値がなくなる。
  なるほど

・上位から比べるのと、下位から比べるのを同時に評価して、先に収束した
 値を返す。
 →これは仕事で使えそうだ。
  CPUのレベルでやるには大変だけど、Verilogとかなら簡単だ。
  ワーストケースが問題になるときには、得意な範囲の違うアルゴリズムを
  2つ同時に動かして先に収束した方を解とする。
  
おもしろいな。

|

« OS自作入門 5日目 | Main | 今日の読書 »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/18154/12074310

Listed below are links to weblogs that reference 先頭から0を数える:

« OS自作入門 5日目 | Main | 今日の読書 »