Haskell Int64 不一致？

Question

我正在尝试解决问题 2 的补码 here (抱歉，需要登录，但任何人都可以使用 FB/google 帐户登录)。简而言之，问题是计算给定范围 [A, B] 内所有数字的 2 补码表示中出现的 1 的数量，其中 A 和 B 在 32 位限制内 (2³¹以绝对值表示)。我知道我的算法是正确的(它是较大绝对值的对数，因为我已经用另一种语言解决了这个问题)。

我正在我的机器上测试下面的代码，它给出了完全正确的结果。当它在亚马逊服务器上运行时，它给出了一些错误的答案(显然是溢出)以及一些堆栈溢出。这不是这里逻辑中的错误，因为我在我的机器上使用相同的测试输入测试相同的代码并得到不同的结果。例如，对于范围 [-1548535525, 662630637]，我在我的机器上得到 35782216444，而根据测试，我的结果是一些负溢出值。

我能想到的唯一问题是，也许我没有正确使用 Int64，或者我对其操作有错误的假设。

感谢任何帮助。代码是here .

Answer 1

堆栈溢出是逻辑中的错误。

countOnes !a !b | a == b = countOnes' a

countOnes' :: Int64 -> Integer
countOnes' !0 = 0
countOnes' !a = (fromIntegral (a .&. 1)) + (countOnes' (a `shiftR` 1))

每当您使用负参数调用 countOnes' 时，您都会得到一个不间断的计算，因为 shiftR 是算术移位而不是逻辑移位，因此您始终会移位为 1 位且永远不会达到 0。 但即使使用逻辑移位，对于负参数，您也会得到结果 32 太大，因为前 32 位都是 1。

解决方案:在调用 countOnes' 之前屏蔽掉不感兴趣的位，

countOnes !a !b | a == b = countOnes' (a .&. 0xFFFFFFFF)

countOnes中有一些多余的守卫，

countOnes :: Int64 -> Int64 -> Integer
countOnes !a !b | a > b = 0
-- From here on we know a <= b
countOnes !a !b | a == b = countOnes' (a .&. 0xFFFFFFFF)
-- From here on, we know a < b
countOnes !0 !n = range + leading  + (countOnes 0 (n - (1 `shiftL` m)))
    where
        range = fromIntegral $ m * (1 `shiftL` (m - 1))
        leading = fromIntegral $ (n - (1 `shiftL` m) + 1)
        m = (getLog n) - 1
-- From here on, we know a /= 0
countOnes !a !b | a > 0 = (countOnes 0 b) - (countOnes 0 (a - 1))
-- From here on, we know a < 0,
-- the guard in the next and the last equation are superfluous
countOnes !a !0 | a < 0 = countOnes (maxInt + a + 1) maxInt
countOnes !a !b | b < 0 = (countOnes a 0) - (countOnes (b + 1) 0)
countOnes !a !b | a < 0 = (countOnes a 0) + (countOnes 0 b)

服务器上的整数溢出是由于

getLog :: Int64 -> Int
--
countOnes !0 !n = range + leading  + (countOnes 0 (n - (1 `shiftL` m)))
    where
    range = fromIntegral $ m * (1 `shiftL` (m - 1))
    leading = fromIntegral $ (n - (1 `shiftL` m) + 1)
    m = (getLog n) - 1

因为服务器有 32 位 GHC，而你有 64 位 GHC。移位距离/位宽m是一个Int(因为它被用作移位距离，所以它必须是)。

因此

m * (1 `shiftL` (m-1))

也是一个Int。对于 m >= 28，会溢出 32 位 Int。

解决方案:删除$

range = fromIntegral m * (1 `shiftL` (m - 1))

那么被移位的1是一个Integer，因此不会溢出。