01

03

[Haskell] 符号なし整数AからBに変換するのに必要なビット数

2013.01.03(10:02)

世界で闘うプログラミング力を鍛える150問
http://www.amazon.co.jp/dp/4839942390/
の問題5.5 をHaskellで解いてみた。

問題5.5 ある整数AからBに変換するのに必要なビット数を決定する関数を書いてください。

HaskellのData.Bitsライブラリにある関数
http://saltheads.blog134.fc2.com/blog-entry-99.html
を使えば1行で書けるけど、あえて3つのアルゴリズムで解いてみた。Haskellでは符号なし整数はWordであり、符号あり整数Intと区別して関数の型宣言をおこなう必要がある。

{-# OPTIONS -Wall -Werror #-}

module BitSwap where
import Test.HUnit
import Test.QuickCheck (quickCheck)
import Data.Bits -- ビット操作、ビット演算ライブラリ
import Data.Word -- 符号なし整数

-- | ------------- 世界で闘うプログラミング力を鍛える150問 -----------------
-- | 問題 5.5 ある整数AからBに変換するのに必要な
-- |          ビット数を決定する関数を書いてください。
-- |          例 入力: 31 14   出力: 2
-- |            つまり、0x1F 0x0E のとき、2 ビット
-- | ----------------------- アルゴリズム1 ---------------------------
bitSwapRequired1 :: Word->Word->Int
bitSwapRequired1 a b = popCount $ xor a b

-- | ----------------------- アルゴリズム2 ---------------------------
bitShiftCount :: Int->Word->Int
bitShiftCount c 0 = c
bitShiftCount c n = bitAndWithDec (c + bit0) (shift n (-1))
                    where bit0 = if testBit n (0::Int) then (1::Int)
                                                       else (0::Int)

bitSwapRequired2 :: Word->Word->Int
bitSwapRequired2 a b = bitShiftCount (0::Int) (xor a b)

-- | ----------------------- アルゴリズム3 ---------------------------
bitAndWithDec :: Int->Word->Int
bitAndWithDec c 0 = c
bitAndWithDec c n = bitAndWithDec (c+1) ((.&.) n (n-1))

bitSwapRequired3 :: Word->Word->Int
bitSwapRequired3 a b = bitAndWithDec 0 (xor a b)

-- | ---------------------- テスト ---------------------------
bitSwapTest :: Test
bitSwapTest = test [
  ((.&.) (6::Word) 3) ~=? (2::Word),    -- ビット論理積
  ((.|.) (6::Word) 3) ~=? (7::Word),    -- ビット論理和
  (xor   (6::Word) 3) ~=? (5::Word),    -- ビット排他的論理和
  (popCount (0x80000000::Word)) ~=? (1::Int), -- 1であるbitの数
  (popCount (0xF0000000::Word)) ~=? (4::Int),
  (popCount (0xFFFFFFFF::Word)) ~=? (32::Int),
  (shift (0x80000000::Int) (-1)) ~=? (0xC0000000::Int), -- 右シフト
  (shift (0x80000000::Word) (-1)) ~=? (0x40000000::Word), -- 右シフト

  (bitSwapRequired1 31 14) ~=? 2,
  (bitSwapRequired2 31 14) ~=? 2,
  (bitSwapRequired3 31 14) ~=? 2,
                True ~=? True
  ]

-- | quickCheck
prop_bitSwap :: Word->Word->Bool
prop_bitSwap a b = 
    (bitSwapRequired1 a b) == (bitSwapRequired2 a b) &&
    (bitSwapRequired1 a b) == (bitSwapRequired3 a b)

main :: IO ()
main = do
       _ <- runTestTT bitSwapTest
       quickCheck prop_bitSwap
       return ()


プロフィール

島敏博

Shima Toshihiro 島敏博
信州アルプスハイランド在住。HaskellとElixirが好き。組み込みソフトウェアアーキテクト、C++プログラマ、山歩き、美術館巡り、和食食べ歩き、日本赤十字社救急法指導員、インデックス投資、クラシック音楽、SESSAME会員、状態マシン設計、モデル駆動開発、ソフトウェアプロダクトライン、Rubyist、実践ビジネス英語

■ ツイッター
http://twitter.com/saltheads
■ Facebook
http://www.facebook.com/saltheads
■ Qiita
http://qiita.com/saltheads

印刷する場合は、ブラウザの印刷メニューではなく、このページの上から3cmくらいの青いところにある、「印刷」を押してみてください。少しうまく印刷できます。まだ完全ではないのですが、これで勘弁してください。


カテゴリ
最新記事
月別アーカイブ
最新コメント
検索フォーム
リンク
sessame
RSSリンクの表示