以二进制补码表示读/写Haskell Integer

Question

我需要以与Java对BigInteger类所做的兼容的方式读写Integers :

返回一个包含此BigInteger的二进制补码表示的字节数组.字节数组将采用big-endian字节顺序:最重要的字节位于第0个元素中.该数组将包含表示此BigInteger所需的最小字节数,包括至少一个符号位,即(ceil((this.bitLength()+ 1)/ 8)).

可悲的是,这排除了Data.Binary提供什么.在库中的某个地方遵循此约定,是否有效地进行ByteString< - > Integer转换？如果没有,怎么办呢？

基于Thomas M. DuBuisson(以及以下讨论)的回答,我现在有了

i2bs :: Integer -> B.ByteString
i2bs x
   | x == 0 = B.singleton 0
   | x < 0 = i2bs $ 2 ^ (8 * bytes) + x
   | otherwise = B.reverse $ B.unfoldr go x
   where
      bytes = (integerLogBase 2 (abs x) + 1) `quot` 8 + 1
      go i = if i == 0 then Nothing
                       else Just (fromIntegral i, i `shiftR` 8)

integerLogBase :: Integer -> Integer -> Int
integerLogBase b i =
     if i < b then
        0
     else
        -- Try squaring the base first to cut down the number of divisions.
        let l = 2 * integerLogBase (b*b) i
            doDiv :: Integer -> Int -> Int
            doDiv i l = if i < b then l else doDiv (i `div` b) (l+1)
        in  doDiv (i `div` (b^l)) l

哪个比我希望的更冗长,仍然错过了这个bs2i功能.

Answer 1

只需从crypto-api 窃取i2bs和bs2i例程,并给它们稍作修改:

import Data.ByteString as B

-- |@i2bs bitLen i@ converts @i@ to a 'ByteString'
i2bs :: Integer -> B.ByteString
i2bs = B.reverse . B.unfoldr (\i' -> if i' == 0 then Nothing
                                                else Just (fromIntegral i', i' `shiftR` 8))


-- |@bs2i bs@ converts the 'ByteString' @bs@ to an 'Integer' (inverse of 'i2bs')
bs2i :: B.ByteString -> Integer
bs2i = B.foldl' (\i b -> (i `shiftL` 8) + fromIntegral b) 0 . B.reverse

您可以通过首先确定位大小并使用原始i2bs序列按顺序构造字节串来提高效率(节省反向成本).

(编辑:我应该注意这不是用Java解析器测试的,但是这个基本的构造应该很容易变异以考虑任何丢失的位).