6

我需要以与 Java 对其BigInteger类所做的兼容的方式读取和写入整数：

返回包含此 BigInteger 的二进制补码表示的字节数组。字节数组将采用大端字节序：最高有效字节位于第零个元素中。该数组将包含表示此 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功能。

4

3 回答 3

6

只需从 crypto-api 中窃取i2bsandbs2i例程并对其进行轻微修改：

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 解析器进行测试，但是这个基本结构应该很容易让你改变以考虑任何丢失的位）。

于 2013-02-24T01:21:33.657 回答
1

好的，因此基于 Thomas M. DuBuisson 的部分答案的完全可行的解决方案是：

bs2i :: B.ByteString -> Integer
bs2i b
   | sign = go b - 2 ^ (B.length b * 8)
   | otherwise = go b
   where
      go = B.foldl' (\i b -> (i `shiftL` 8) + fromIntegral b) 0
      sign = B.index b 0 > 127

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

我不会很快接受我自己的答案，以防有人想提出更简洁的东西来展示他的技能。:-)

于 2013-02-24T09:48:28.327 回答
0

这是一个无需先计算大小的解决方案。对于负数，它相当于反转所有位，执行计算，然后再次反转位。

i2bs :: Integer -> B.ByteString
i2bs x = B.reverse . B.unfoldr (fmap go) . Just $ changeSign x
  where
    changeSign :: Num a => a -> a
    changeSign | x < 0     = subtract 1 . negate
               | otherwise = id
    go :: Integer -> (Word8, Maybe Integer)
    go x = ( b, i )
      where
        b = changeSign (fromInteger x)
        i | x >= 128  = Just (x `shiftR` 8 )
          | otherwise = Nothing

bs2i :: B.ByteString -> Integer
bs2i xs = changeSign (B.foldl' go 0 xs)
  where
    changeSign :: Num a => a -> a
    changeSign | B.index xs 0 >= 128 = subtract 1 . negate
               | otherwise           = id
    go :: Integer -> Word8 -> Integer
    go i b = (i `shiftL` 8) + fromIntegral (changeSign b)
于 2013-02-24T22:57:00.213 回答