スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#雑記 Bigger power of two

anarchy golf にBigger power of twoという問題があります。
「与えられた正の整数に対して、それを超える最小の2のべき乗を返せ」という問題です。
 
例えば
3->4
1->2
4->8
2->4
となります。
 
ビット演算を使ってやってみます。
考え方は単純で、与えられた数の最高位のオンになっているビットの位置を見つけます。このとき、下から(その位置+1)番目のビットだけオンになっている数を返すという方法です。
 
まず最上位のビットがオンになっているかどうかを調べる関数を定義します。
 
> let isHighestBitOn n =
    if ((n <<< 1) >>> 1) <> n then true
    else false;;
 
val isHighestBitOn : int -> bool
 
 
次に上から何番目が初めてオンになっているかを返す関数を定義します。
(一番最初は0番目)
 
> //0は渡さないこと(無限ループに陥ります)
let rec indexOfHBO shiftedNum n =
      if isHighestBitOn n then 
         shiftedNum
      else 
         indexOfHBO (shiftedNum + 1) (n <<< 1) ;;
 
val indexOfHBO : int -> int -> int
 
ちょっと使ってみます。
 
> indexOfHBO 0 1 ;;
val it : int = 30
 
うまくいきません。一番下(31番目)が初めてオンになっているので、31が返るはずですが、ダメです。
どこが原因なのでしょう。
これは、符号付きの数をシフトするときは算術シフトになるのが原因です。
論理シフトで考えたいので、uint32を使うことにします。
 
> let isHighestBitOn (n:uint32) =
    if ((n <<< 1) >>> 1) <> n then true
    else false
 
//0は渡さないこと
let rec indexOfHBO shiftedNum n =
      if isHighestBitOn n then 
         shiftedNum
      else 
         indexOfHBO (shiftedNum + 1) (n <<< 1);;
 
val isHighestBitOn : uint32 -> bool
val indexOfHBO : int -> uint32 -> int
 
(実行例)
> indexOfHBO 0 1u ;;
val it : int = 31
 
これで思い通りの結果が得られましたので、目的の関数を定義します。
 
> let getBiggerPowerTwo (n:int) =
    if n <= 0 then 
        failwith "input Error"
    else (1 <<< (32 - (indexOfHBO 0 ((uint32)n)))) ;;
 
val getBiggerPowerTwo : int -> int32
 
(intのままで攻めて2行上の32を31にしてもよいかもしれません)
 
では使ってみます。
 
> [1 .. 32]
|> List.iter (fun i -> printfn "%2d -> %2d" i (getBiggerPowerTwo i));;
 1 ->  2
 2 ->  4
 3 ->  4
 4 ->  8
 5 ->  8
 6 ->  8
 7 ->  8
 8 -> 16
 9 -> 16
10 -> 16
11 -> 16
12 -> 16
13 -> 16
14 -> 16
15 -> 16
16 -> 32
17 -> 32
18 -> 32
19 -> 32
20 -> 32
21 -> 32
22 -> 32
23 -> 32
24 -> 32
25 -> 32
26 -> 32
27 -> 32
28 -> 32
29 -> 32
30 -> 32
31 -> 32
32 -> 64
val it : unit = ()
 
 
コードは以下の通りです。
 
let isHighestBitOn (n:uint32) =
    if ((n <<< 1) >>> 1) <> n then true
    else false
 
//0は渡さないこと
let rec indexOfHBO shiftedNum n =
      if isHighestBitOn n then 
         shiftedNum
      else 
         indexOfHBO (shiftedNum + 1) (n <<< 1) 
 
let getBiggerPowerTwo (n:int) =
    if n <= 0 then 
        failwith "input Error"
    else (int32)(1 <<< (32 - (indexOfHBO 0 ((uint32)n))))
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

trackback


この記事にトラックバックする(FC2ブログユーザー)

Bigger power of two

【F#】Bigger power of two

コメントの投稿

非公開コメント

No title

let isHighestBitOn n = n &&& 0x80000000 <> 0
にすれば、int のままでOK

最上位ビットと同じに0になるまで右シフトして、
その間1を左ビットシフトすれば、
おなじ意味で、色々と省略できる。
let BP2 n =
let rec f n ret=
if n = 0 then
ret
else
f (n >>> 1) (ret <<< 1)
f n 1

No title

コメントありがとうございます。とても勉強になります。
プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。