Haskell Int64 несовместим?

Question

Я пытаюсь решить проблему с дополнением 2 здесь (извините, требуется вход в систему, но любой может войти в систему с учетной записью FB / google).Короче говоря, проблема заключается в подсчете числа единиц, встречающихся в представлении дополнения 2 всех чисел в данном диапазоне [A, B], где A и B находятся в пределах 32-битных пределов (2 ³¹ вабсолютная величина).Я знаю, что мой алгоритм правильный (он логарифмический в большем абсолютном значении, поскольку я уже решил проблему на другом языке).

Я тестирую приведенный ниже код на своей машине, и он дает совершенно правильные результаты.Когда он работает на сервере Amazon, он дает несколько неправильных ответов (очевидно, переполнения), а также некоторые переполнения стека.Это не ошибка в логике, потому что я тестирую один и тот же код на моей машине на одних и тех же тестовых входах и получаю разные результаты.Например, для диапазона [-1548535525, 662630637] я получаю 35782216444 на моей машине, в то время как согласно тестам мой результат - некоторое отрицательное значение переполнения.Я не использую Int64 правильно, или у меня неверное предположение о его работе.

Любая помощь приветствуется.Код здесь .

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-разрядный.Расстояние сдвига / ширина в битах m - это Int (и поскольку оно используется в качестве расстояния сдвига, оно должно быть).

Следовательно,

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

- это Int тоже.Для m >= 28, который переполняет 32-битный Int.

Решение: удалить $

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

Тогда смещенное 1 будет Integerследовательно, переполнения нет.