将二进制转换为负二进制

Question

我需要将正二进制转换为负二进制。我的方法似乎错了。将元素添加到列表的末尾也不起作用。请帮帮我!

twoComplement :: [Int] -> [Int]
twoComplement (x:xs)    | (x:xs) == [] = [x]
                    | last (x:xs) == 0 = (twoComplement (init (x:xs))) ++ [1]
                    | last (x:xs) == 1 = (twoComplement (init (x:xs))) ++ [0]

如你所见，我是哈斯克尔的新手。

Answer 1

在维基百科上，有一个关于如何执行“从LSB到MSB”的补码转换的解释：

从LSB到MSB的工作： 手动将二进制数字转换为其两个补码的快捷方式是从最小有效位( LSB )开始，复制所有零(从LSB到最重要位)，直到到达前1为止；然后复制该1，并翻转所有剩余位。

该算法非常巧妙地翻译成Haskell：

twosComplement :: [Int] -> [Int]
twosComplement bs = zs ++ fixup rest
  where
    (zs, rest) = span (== 0) bs

    fixup [] = []
    fixup (x:xs) = x : map (1-) xs

这个实现使用@chi在他的回答中建议的小endian格式:一般来说，这是处理二进制数字时要使用的格式。如果您真的想要将它保持在大端格式，那么您必须在应用上面定义的twosComplement之前和之后反转这个数字。

执行情况说明

• span用于获取所有连续的最小有效零(zs)以及数字的rest。
• fixup复制遇到的第一个1 (如果它存在的话，它将处于rest的首位)，然后再倒转其他的数字。

Answer 2

(x:xs) == []总是错误的:第一个是至少有一个元素(x)的列表，第二个是空的。

也许你想写点什么

twoComplement [x] = [x]
twoComplement (x:xs)| last (x:xs) == 0 = (twoComplement (init (x:xs))) ++ [1]
                    | last (x:xs) == 1 = (twoComplement (init (x:xs))) ++ [0]

但这看上去还是不对。

我会先定义一个函数来反转一点

invertBit :: Int -> Int
invertBit 0 = 1
invertBit 1 = 0

然后，twoComplement可以通过对所有列表元素应用inverBit来完成，2)调用刚刚获得的二进制数。我会为最后一个写一个单独的函数。

使用一个小的endian表示法也很方便，首先使用最不重要的位--这简化了最后一个增量。