1

8 ビット数値を使用するときに基本的な操作をシミュレートするのに役立つ関数を定義しようとしていました。

これを理解するのに苦労しています..何もインポートせずにできるだけシンプルにしようとしているので、8 つの要素 (0 と 1) の 2 つのリストから始めました。

私が間違っていなければ、次のようになります。

bitsum :: [Int] -> [Int] -> [Int]
bitsum [][] = []

この最後の行の後、リストの要素を 1 対 1 で追加することができないため、ややこしくなり始めます。

bitsum (x:xs)(y:ys)

それが私が今持っているすべてで、正しいと思います。

私の考えは、次のようなことを試すことでした：

bitsum :: [Int] -> [Int] -> [Int]
bitsum [][] = []
bitsum (x:xs)[] = (x:xs)
bitsum [](y:ys) = (y:ys)
bitsum (x:xs)(y:ys) | (x:xs) == (y:ys) && < 0 = (x:xs)
                    | (x:xs) == (y:ys) && > 0 =

しかし、私はどこかで間違った方向に進んでいると思います。

誰かがこの問題を手伝ってくれたら本当にありがたいです。

4

3 に答える 3

2

これにはキャリーは不要です。ビットごとのバイナリ加算の 2 つのプロパティに注意してください。上位桁は AND で指定され、下位桁は XOR で指定されます。これらは：

xor a b = if a == b then 0 else 1

and' 1 1 = 1 -- `and` is a function in Prelude.
and' _ _ = 0

2 進数の合計を求めるには、単純にビット単位の xor と を取り、それぞれ下位桁と上位桁を見つけます。上位桁 (エンディアンに応じて左または右) をシフトし、その合計と下位桁を取得します。

リトルエンディアン:

bitsum0 :: [Int] -> [Int] -> [Int]
bitsum0 xs ys
    | (sum xs) == 0 = ys
    | (sum ys) == 0 = xs
    | otherwise = bitsum0 low (0:high)
        where low = zipWith xor xs ys
              high = zipWith and' xs ys

ビッグエンディアン:

bitsum1 :: [Int] -> [Int] -> [Int]
bitsum1 xs ys
    | (sum xs) == 0 = ys
    | (sum ys) == 0 = xs
    | otherwise = bitsum1 low ((tail high) ++ [0])
        where low = zipWith xor xs ys
              high = zipWith and' xs ys

各関数の 2 つのガードにより、終了が保証されます。最終的に、再帰は x+0 を追加することになり、これで終了です。

エラーチェックは行われないことに注意してください。異なる長さのオーバーフローとリスト (および null リスト) は未定義の動作です。リストが無意味なゴミでいっぱいになる可能性があります (特に、and'0 を 0 として扱い、その他すべてを 1 として扱います)。おそらく、次のようなものを使用する方がより実用的でしょう

data Bit = Bool
type Word_8 = (Bit , Bit , Bit , Bit , Bit , Bit , Bit , Bit )

またはさらに良い

import Data.Word
binsum :: Word8 -> Word8 -> Word8
binsum = (+)
于 2013-07-13T02:40:49.507 に答える
2

キャリービットが必要になります。列ごとに追加することはできません。少しずつやってみましょう：

bitsum :: [Int] -> [Int] -> [Int]
bitsum = bitsum' 0
  where
    bitsum' _ [] [] = []

スタートがあります。キャリーなしで開始し、追加するビットがもうない場合を扱います。両方のビットが 0 の場合はどうなるでしょうか。

    bitsum' 0 (0:xs) (0:ys) = 0 : bitsum' 0 xs ys
    bitsum' 1 (0:xs) (0:ys) = 1 : bitsum' 0 xs ys

両方とも 0 で、キャリーが 0 の場合、そのビットの結果は 0 で、キャリーはありません。キャリーがあればそれを使用し、キャリーなしで続行します。

    bitsum' 0 (1:xs) (1:ys) = 0 : bitsum' 1 xs ys
    bitsum' 1 (1:xs) (1:ys) = 1 : bitsum' 1 xs ys

それらが1つである場合、それは似ています。常にキャリーがあることを除いて。そして、それらが異なる場合：

    bitsum' 0 (x:xs) (y:ys) = 1 : bitsum' 0 xs ys
    bitsum' 1 (x:xs) (y:ys) = 0 : bitsum' 1 xs ys

他のすべてのケースを扱ったので、これらは 0 と 1 でなければなりません。合計すると 1 になります。そこからどうあるべきかが見えてきます。上記のいくつかのパターンが見られるようになったので、これをすべて要約して、より短い答えにすることができます。

bitsum :: [Int] -> [Int] -> [Int]
bitsum = bitsum' 0
  where
    bitsum' _ [] [] = []
    bitsum' carry (x:xs) (y:ys) | x == y = carry : bitsum' x xs ys
                                | otherwise = (1 - carry) : bitsum' carry xs ys

(1-carry) は、1 を 0 に、またはその逆に反転させるための凝った方法です。その場合、ビットは常にキャリーの反対になるからです。

于 2013-07-12T01:11:40.080 に答える
0

これは、Haskell での非常に単純なゲート表現です。Haskell の学習を始めたばかりなので、形式はシンプルで、どのように学習しているか.. 数学で少しシミュレーションを作成するのが楽しそうだったので、これを一緒にハックしました.. 誰かの役に立てば幸いです :)

andGate x y = [z | z <- [if (x == 1 && y == 1) then 1 else 0]]

orGate x y = [z | z <- [if (x == 1 || y == 1) then 1 else 0]]

nandGate x y = [z | q <- (andGate x y), z <- [if (q == 0) then 1 else 0 ]]

norGate x y  = [z | q <- (orGate x y), z <- [if (q == 0) then 1 else 0 ]]

xorGate x y  = [z | 
 xn <- [if (x == 0) then 1 else 0], 
 yn <- [if (y == 0) then 1 else 0],
 q  <- (andGate xn y), 
 p  <- (andGate x yn), 
 z  <- (orGate q p)]

xnorGate x y  = [z | 
 xn <- [if (x == 0) then 1 else 0], 
 yn <- [if (y == 0) then 1 else 0],
 q  <- (andGate xn yn), 
 p  <- (andGate x y), 
 z  <- (orGate q p)]

halfAdder a b = [ (x, y) | x <- (xorGate a b), y <- (andGate a b)]

fullAdder a b c = [ (sum, cout) |
 u1     <- xorGate a b,
 u2     <- andGate a b,
 sum    <- xorGate u1 c,
 u4     <- andGate u1 c,
 cout   <- orGate u4 u2]
于 2016-12-07T13:13:50.463 に答える