CODEWITHSUNDEEP
haskellbinary
04k
04k

Reputation: 53

Converting binary to negative binary

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.

Upvotes: 0

Views: 1870

Answers (2)

amnn
amnn

Reputation: 3716

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.

Upvotes: 2

chi
chi

Reputation: 116139

(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.

Upvotes: 1

Related Questions