0

I need to convert a positive binary to a negative binary. My approach seems somehow wrong. Adding an element to the end of a list does not work too. Please help me!

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]

as u see I'm new to haskell.

04k
  • 53
  • 7

2 Answers2

2

Looking on Wikipedia, there's an explanation of how to perform the two's complement conversion "From LSB to MSB":

Working from LSB towards MSB:

A shortcut to manually convert a binary number into its two's complement is to start at the least significant bit (LSB), and copy all the zeros (working from LSB toward the most significant bit) until the first 1 is reached; then copy that 1, and flip all the remaining bits.

This algorithm translates quite neatly to Haskell:

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

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

This implementation is using the little-endian format that @chi suggested in his answer: In general that is the one you want to use when processing binary numbers. If you really really want to keep it in big-endian format, then you will have to reverse the number before and after applying twosComplement as defined above.

Implementation Notes

  • span is used to get all the consecutive least significant zeros (zs) as well as the rest of the number.
  • fixup copies the first 1 encountered (it will be at the head of rest if it exists at all), before inverting the rest of the number.
amnn
  • 3,657
  • 17
  • 23
  • 1
    I suggest you rename `fix` to `fixup` or similar. Most Haskell programmers will assume at first that you mean `Data.Function.fix`. That is, `fix f = let g = f g in g` – dfeuer Nov 15 '15 at 04:01
  • 1
    Also, it's probably more efficient to use `invert x = 1 - x`. – dfeuer Nov 15 '15 at 04:03
  • Ah thanks ;) I initially named `fix`, `flip`... lots of shadowing going on over here. – amnn Nov 15 '15 at 09:37
1

(x:xs) == [] is always false: the first is a list having at least one element (x) and the second is empty.

Maybe you wanted to write something like

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

but this still looks wrong.

I would define a function to invert a bit first

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

then, twoComplement can be done by 1) applying inverBit on all the list elements, and 2) invrementing the binary number just obtained. I'd write a separate function for the last.

It might also be convenient to use a little endian notation, with the least significant bit first -- that simplifies the last increment.

chi
  • 111,837
  • 3
  • 133
  • 218
  • Pattern matching over `(:)` is unnecessary, every instance of `(x:xs)` can be replaced with just `xs`. (But then converting to little endian you notice that `twoComplement = map invertBit` too). – amnn Nov 08 '15 at 11:04