1 {-# OPTIONS -fno-implicit-prelude #-}
2 -----------------------------------------------------------------------------
5 -- Copyright : (c) The University of Glasgow 2001
6 -- License : BSD-style (see the file libraries/base/LICENSE)
8 -- Maintainer : libraries@haskell.org
9 -- Stability : experimental
10 -- Portability : portable
12 -- This module defines bitwise operations for signed and unsigned
13 -- integers. Instances of the class 'Bits' for the 'Int' and
14 -- 'Integer' types are available from this module, and instances for
15 -- explicitly sized integral types are available from the
16 -- "Int" and "Word" modules.
18 -----------------------------------------------------------------------------
22 (.&.), (.|.), xor, -- :: a -> a -> a
23 complement, -- :: a -> a
24 shift, -- :: a -> Int -> a
25 rotate, -- :: a -> Int -> a
27 setBit, -- :: a -> Int -> a
28 clearBit, -- :: a -> Int -> a
29 complementBit, -- :: a -> Int -> a
30 testBit, -- :: a -> Int -> Bool
31 bitSize, -- :: a -> Int
32 isSigned, -- :: a -> Bool
33 shiftL, shiftR, -- :: a -> Int -> a
34 rotateL, rotateR -- :: a -> Int -> a
38 -- instance Bits Integer
41 -- Defines the @Bits@ class containing bit-based operations.
42 -- See library document for details on the semantics of the
43 -- individual operations.
45 #ifdef __GLASGOW_HASKELL__
52 infixl 8 `shift`, `rotate`, `shiftL`, `shiftR`, `rotateL`, `rotateR`
58 The 'Bits' class defines bitwise operations over integral types.
60 * Bits are numbered from 0 with bit 0 being the least
63 class Num a => Bits a where
73 {-| Reverse all the bits in the argument -}
76 {-| Shift the argument left by the specified number of bits.
77 Right shifts (signed) are specified by giving a negative value.
79 An instance can define either this unified 'shift' or 'shiftL' and
80 'shiftR', depending on which is more convenient for the type in
82 shift :: a -> Int -> a
84 x `shift` i | i<0 = x `shiftR` (-i)
88 {-| Rotate the argument left by the specified number of bits.
89 Right rotates are specified by giving a negative value.
91 'rotate' is well defined only if 'bitSize' is also well defined
92 ('bitSize' is undefined for 'Integer', for example).
94 An instance can define either this unified 'rotate' or 'rotateL' and
95 'rotateR', depending on which is more convenient for the type in
97 rotate :: a -> Int -> a
99 x `rotate` i | i<0 = x `rotateR` (-i)
101 | i>0 = x `rotateL` i
104 -- Rotation can be implemented in terms of two shifts, but care is
105 -- needed for negative values. This suggested implementation assumes
106 -- 2's-complement arithmetic. It is commented out because it would
107 -- require an extra context (Ord a) on the signature of 'rotate'.
108 x `rotate` i | i<0 && isSigned x && x<0
109 = let left = i+bitSize x in
110 ((x `shift` i) .&. complement ((-1) `shift` left))
112 | i<0 = (x `shift` i) .|. (x `shift` (i+bitSize x))
114 | i>0 = (x `shift` i) .|. (x `shift` (i-bitSize x))
117 -- | @bit i@ is a value with the @i@th bit set
120 -- | @x \`setBit\` i@ is the same as @x .|. bit i@
121 setBit :: a -> Int -> a
123 -- | @x \`clearBit\` i@ is the same as @x .&. complement (bit i)@
124 clearBit :: a -> Int -> a
126 -- | @x \`complementBit\` i@ is the same as @x \`xor\` bit i@
127 complementBit :: a -> Int -> a
129 -- | Return 'True' if the @n@th bit of the argument is 1
130 testBit :: a -> Int -> Bool
132 {-| Return the number of bits in the type of the argument. The actual
133 value of the argument is ignored -}
136 {-| Return 'True' if the argument is a signed type. The actual
137 value of the argument is ignored -}
138 isSigned :: a -> Bool
141 x `setBit` i = x .|. bit i
142 x `clearBit` i = x .&. complement (bit i)
143 x `complementBit` i = x `xor` bit i
144 x `testBit` i = (x .&. bit i) /= 0
146 {-| Shift the argument left by the specified number of bits
147 (which must be non-negative).
149 An instance can define either this and 'shiftR' or the unified
150 'shift', depending on which is more convenient for the type in
152 shiftL :: a -> Int -> a
153 x `shiftL` i = x `shift` i
155 {-| Shift the argument right (signed) by the specified number of bits
156 (which must be non-negative).
158 An instance can define either this and 'shiftL' or the unified
159 'shift', depending on which is more convenient for the type in
161 shiftR :: a -> Int -> a
162 x `shiftR` i = x `shift` (-i)
164 {-| Rotate the argument left by the specified number of bits
165 (which must be non-negative).
167 An instance can define either this and 'rotateR' or the unified
168 'rotate', depending on which is more convenient for the type in
170 rotateL :: a -> Int -> a
171 x `rotateL` i = x `rotate` i
173 {-| Rotate the argument right by the specified number of bits
174 (which must be non-negative).
176 An instance can define either this and 'rotateL' or the unified
177 'rotate', depending on which is more convenient for the type in
179 rotateR :: a -> Int -> a
180 x `rotateR` i = x `rotate` (-i)
182 #ifdef __GLASGOW_HASKELL__
183 instance Bits Int where
184 (I# x#) .&. (I# y#) = I# (word2Int# (int2Word# x# `and#` int2Word# y#))
185 (I# x#) .|. (I# y#) = I# (word2Int# (int2Word# x# `or#` int2Word# y#))
186 (I# x#) `xor` (I# y#) = I# (word2Int# (int2Word# x# `xor#` int2Word# y#))
187 complement (I# x#) = I# (word2Int# (int2Word# x# `xor#` int2Word# (-1#)))
188 (I# x#) `shift` (I# i#)
189 | i# >=# 0# = I# (x# `iShiftL#` i#)
190 | otherwise = I# (x# `iShiftRA#` negateInt# i#)
191 (I# x#) `rotate` (I# i#) =
192 I# (word2Int# ((x'# `shiftL#` i'#) `or#`
193 (x'# `shiftRL#` (wsib -# i'#))))
196 i'# = word2Int# (int2Word# i# `and#` int2Word# (wsib -# 1#))
197 wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
198 bitSize _ = WORD_SIZE_IN_BITS
201 instance Bits Integer where
202 (S# x) .&. (S# y) = S# (word2Int# (int2Word# x `and#` int2Word# y))
203 x@(S# _) .&. y = toBig x .&. y
204 x .&. y@(S# _) = x .&. toBig y
205 (J# s1 d1) .&. (J# s2 d2) =
206 case andInteger# s1 d1 s2 d2 of
209 (S# x) .|. (S# y) = S# (word2Int# (int2Word# x `or#` int2Word# y))
210 x@(S# _) .|. y = toBig x .|. y
211 x .|. y@(S# _) = x .|. toBig y
212 (J# s1 d1) .|. (J# s2 d2) =
213 case orInteger# s1 d1 s2 d2 of
216 (S# x) `xor` (S# y) = S# (word2Int# (int2Word# x `xor#` int2Word# y))
217 x@(S# _) `xor` y = toBig x `xor` y
218 x `xor` y@(S# _) = x `xor` toBig y
219 (J# s1 d1) `xor` (J# s2 d2) =
220 case xorInteger# s1 d1 s2 d2 of
223 complement (S# x) = S# (word2Int# (int2Word# x `xor#` int2Word# (0# -# 1#)))
224 complement (J# s d) = case complementInteger# s d of (# s, d #) -> J# s d
226 shift x i | i >= 0 = x * 2^i
227 | otherwise = x `div` 2^(-i)
229 rotate x i = shift x i -- since an Integer never wraps around
231 bitSize _ = error "Bits.bitSize(Integer)"
236 instance Bits Int where
237 (.&.) = nhc_primIntAnd
238 (.|.) = nhc_primIntOr
240 complement = nhc_primIntCompl
241 shiftL = nhc_primIntLsh
242 shiftR = nhc_primIntRsh
246 foreign import ccall nhc_primIntAnd :: Int -> Int -> Int
247 foreign import ccall nhc_primIntOr :: Int -> Int -> Int
248 foreign import ccall nhc_primIntXor :: Int -> Int -> Int
249 foreign import ccall nhc_primIntLsh :: Int -> Int -> Int
250 foreign import ccall nhc_primIntRsh :: Int -> Int -> Int
251 foreign import ccall nhc_primIntCompl :: Int -> Int
253 instance Bits Integer where
254 -- (.&.) a b = undefined
255 -- (.|.) a b = undefined
256 -- xor a b = undefined
258 x `shift` i | i<0 = x `div` (2^(-i))
261 x `rotate` i = x `shift` i -- an Integer never wraps
262 bitSize _ = error "Data.Bits: bitSize :: Integer -> Int"