Problem 323 「ランダムな整数のビット論理和演算」

y0, y1, y2,... を, ランダムな 32 ビット符号なし整数からなる数列とする.
(つまり 0≦yi<232 で全ての値が同様に確からしい. )

数列 xi に対し次の反復が与えられる:

  • x0 = 0
  • xi = xi-1 | yi-1 (i>0)(| はビット単位のOR演算)

すべての i≧N に対し xi = 232-1(ビットがすべて1となるパターン)となるような添え字 N が最終的に存在することが分かる.

N の期待値を求めよ.
答を小数点以下 10 桁に四捨五入して求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2011-02-06 (日) 20:57:01 (2244d)