6

Java がBigIntegerクラスで行うことと互換性のある方法で Integers を読み書きする必要があります。

この BigInteger の 2 の補数表現を含むバイト配列を返します。バイト配列はビッグ エンディアンのバイト順になります。最上位バイトは 0 番目の要素にあります。配列には、少なくとも 1 つの符号ビット (ceil((this.bitLength() + 1)/8)) を含む、この BigInteger を表すために必要な最小バイト数が含まれます。

悲しいことに、これは提供するものを除外し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から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パーサーでテストされていないことに注意してください。ただし、この基本的な構成は、欠落しているビットを考慮して変更するのが簡単なはずです）。

于 2013-02-24T01:21:33.657 に答える
1

Ok, so a fully working solution based on the partial answer by Thomas M. DuBuisson is:

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

I won't accept my own answer anytime soon in case someone wants to come up with something more neat to show of his skills. :-)

于 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 に答える