Haskell二进制div二进制

Question

我正在写一个程序，它可以将十进制数、字符、字符串转换为二进制数，并使用它们。但是我被卡住了，因为我想除以Bin。如下所示：

  11010110110000
/ 10011
  --------------
= 01001110110000 

所以新的数字将是1001110110000 / 10011...直到最后的结果。

下面是我的代码：

import Data.Char (ord)
import Data.List

toBinary :: Int -> [Int]
toBinary 0 = []
toBinary x = reverse (kisegf x)

kisegf 0 = []
kisegf x | x `mod` 2 == 1 = 1 : kisegf (x `div` 2)
         | x `mod` 2 == 0 = 0 : kisegf (x `div` 2)

chrToBinary :: Char -> [Int]    
chrToBinary x 
                |length (toBinary (ord x)) == 8 = (toBinary (ord x)) 
                |otherwise = take (8-(length (toBinary (ord x))))[0,0..] ++ (toBinary (ord x))

strToBinary :: String -> [Int]
strToBinary [] = []
strToBinary (x:xs) = [l | l <- chrToBinary x] ++ strToBinary xs

bxor :: [Int] -> [Int] -> [Int]
bxor [] [] = []
bxor (x:xs) (y:ys)
            |length (x:xs) == length (y:ys) && (x /= y) = 1 : bxor xs ys
            |length (x:xs) == length (y:ys) && (x == y) = 0 : bxor xs ys
            |length (x:xs) < length (y:ys) && (x /= y) = 1 : bxor (take (length (y:ys)-(length (x:xs)))[0,0..] ++ xs) ys
            |length (x:xs) < length (y:ys) && (x == y) = 0 : bxor (take (length (y:ys)-(length (x:xs)))[0,0..] ++ xs) ys
            |length (x:xs) > length (y:ys) && (x /= y) = 1 : bxor xs (take (length (x:xs)-(length (y:ys)))[0,0..] ++ ys)
            |length (x:xs) > length (y:ys) && (x == y) = 0 : bxor xs (take (length (x:xs)-(length (y:ys)))[0,0..] ++ ys)
{-this will compare 2 bin if a bigger than true else false-}
(%>=%) :: [Int] -> [Int] -> Bool
(%>=%)[] [] = True
(%>=%)[] _ = False
(%>=%)_ [] = True
(%>=%) (x:xs) (y:ys) = x==1 && y==1 && elemIndex 1 (x:xs) == elemIndex 1 (y:ys)

bmod :: [Int]{-number-} -> [Int]{-div-} -> [Int]{-result-}
bmod (x:xs) (y:ys)
            |length(x:xs) >= length(y:ys) && (take (length (y:ys)) (x:xs)) %>=% (y:ys) = ???
            |length(x:xs) >= length(y:ys) = ???
            |otherwise = (x:xs)

我应该写什么来代替“？”

另一个更大的例子：

Példa: bmod 11010110110000 10011.

       _______________
10011 ) 11010110110000
        10011,,.,,....
        -----,,.,,....
         10011,.,,....
         10011,.,,....
         -----,.,,....
          00001.,,....
          00000.,,....
          -----.,,....
           00010,,....
           00000,,....
           -----,,....
            00101,....
            00000,....
            -----,....
             01011....
             00000....
             -----....
              10110...
              10011...
              -----...
               01010..
               00000..
               -----..
                10100.
                10011.
                -----.
                 01110  
                 10011  <- bigger so cant div again
                 -----
                  1110 = what i want

Answer 1

你所写的函数并不是你想要的。

bmod xs ys | not (xs %>=% ys) = xs
           | otherwise = ????

可能会工作得更好。在?中，您希望从xs的开头开始获取连续的位数，直到您发现xs的前缀大于ys，然后使用递归

bmod ((xsPrefix %-% ys)++xsSuffix) ys

要获得xs的前缀，结合使用inits和filter就足够了。显然，您还需要实现更多的二进制函数。

您的设计的问题是在第二种情况下没有什么可递归的--您希望以某种方式使用第一种情况下的代码，但除了复制代码之外，没有一种简单的方法可以做到这一点。

此外，您的kisegf函数可以稍微清理一下--为什么不呢

kisegf 0 = []
kisegf x = (x `mod` 2) : kisegf (x `div` 2)

Answer 2

虽然不能回答你的问题，但我会先保留位串LSB，而不是MSB (即不要在toBinary中使用reverse )。通过这种方式，列表索引对应于位重要性，因此您不必担心添加前导零来对齐操作数。例如，bxor函数变得简单得多：

bxor [] bs = bs
bxor as [] = as
bxor (a:as) (b:bs) = (a `xor` b) : bxor as bs where
  a `xor` b | a /= b    = 1
            | otherwise = 0

由于进位从LSB传播到MSB，因此具有这种顺序的位还将使加法/减法更简单：

badd :: [Int] {- a -} -> [Int] {- b -} -> Int {- carry-in -} -> [Int]
badd []     []     0 = []  -- no carry-out
badd []     []     1 = [1] -- carry-out
badd []     (b:bs) c = s : badd [] bs c' where (c', s) = add 0 b c -- zero-extend as
badd (a:as) []     c = s : badd as [] c' where (c', s) = add a 0 c -- zero-extend bs
badd (a:as) (b:bs) c = s : badd as bs c' where (c', s) = add a b c

add a b c = (s `div` 2, s `mod` 2) where s = a+b+c

左移位和右移位也更简单，因为它们影响LSB：

as `rsh` n = drop n as
as `lsh` n = replicate n 0 ++ as

对于有符号的数字，您隐含地假设最后一位无限重复。