fork download
copy 
  1. {-# LANGUAGE BangPatterns #-}
  2. import Data.Bits
  3. import Data.List
  4. import Data.Maybe
  5. import Data.Int
  6. import Control.Monad
  7.  
  8. maxInt :: Int64
  9. maxInt = 4294967295
  10.  
  11. countOnes' :: Int64 -> Integer
  12. countOnes' !0 = 0
  13. countOnes' !a = (fromIntegral (a .&. 1)) + (countOnes' (a `shiftR` 1))
  14.  
  15. getLog :: Int64 -> Int
  16. getLog !n = fromJust $ findIndex (> n) $ map (1 `shiftL`) [0..]
  17.  
  18. countOnes :: Int64 -> Int64 -> Integer
  19. countOnes !a !b | a > b = 0
  20. countOnes !a !b | a == b = countOnes' a
  21. countOnes !0 !n = range + leading  + (countOnes 0 (n - (1 `shiftL` m)))
  22.     where
  23.         range = fromIntegral $ m * (1 `shiftL` (m - 1))
  24.         leading = fromIntegral $ (n - (1 `shiftL` m) + 1)
  25.         m = (getLog n) - 1
  26. countOnes !a !b | a > 0 = (countOnes 0 b) - (countOnes 0 (a - 1))
  27. countOnes !a !0 | a < 0 = countOnes (maxInt + a + 1) maxInt
  28. countOnes !a !b | b < 0 = (countOnes a 0) - (countOnes (b + 1) 0)
  29. countOnes !a !b | a < 0 = (countOnes a 0) + (countOnes 0 b)
  30.  
  31. splitBy :: Char -> String -> [String]
  32. splitBy _ [] = []
  33. splitBy c s = first : splitBy c (dropWhile (== c) rest)
  34.     where
  35.         (first, rest) = break (== c) s
  36.  
  37. readLineInt :: IO Int
  38. readLineInt = getLine >>= return . read
  39.  
  40. readLineInts :: IO [Int64]
  41. readLineInts = getLine >>= return . map read . (splitBy ' ')
  42.  
  43. main :: IO ()
  44. main = do
  45.     n <- readLineInt
  46.     doIt n
  47.  
  48. doIt :: Int -> IO ()
  49. doIt !0 = return ()
  50. doIt !n = do
  51.     l <- readLineInts
  52.     putStrLn $ show $ countOnes (head l) (head $ tail l)
  53.     doIt (n - 1)
  54.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1Okyn
language:
Haskell (ghc 8.4.4)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!